COCI '22 Contest 2 #3 Lampice

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem type

Christmas is coming! Teo has already decided to decorate his terrace.

Teo has a big rectangular-shaped terrace. It is n meters long and m meters wide. Teo has decided to decorate his terrace in a very strange way. Instead of hanging Christmas lights on the edges of his terrace, he will put them on the floor!

Teo has 2k lamps, two per each of k colours. He will put each in some position (x_i, y_i), where x_i represents the distance from the left side of the terrace and y_i from the bottom side.

Proud of how he decorated the terrace, he decided to take the rest of his day off. But soon, he got bored, so he returned to the terrace. He started counting nice rectangles on the terrace. A rectangle is nice if, for each colour, both lamps are either inside or outside of the rectangle. If a lamp is located on the rectangle edge, it is considered to be inside of it.

The left rectangle is not nice. One blue lamp is inside the rectangle, and one is outside.
The right rectangle is nice. Red and blue lamps are inside. Yellow lamps are outside.

Teo has realized that counting nice rectangles is not an easy job. He is interested in how many nice rectangles are there, whose corners have integer distances from the bottom and left sides of the terrace. All rectangles we consider are parallel with terrace sides. This is where you step in! Count the number of nice rectangles.

Input Specification

The first line contains three integers n, m, k (1 \le n \le 150, 1 \le m \le 1\,000, 0 \le k \le 200\,000), the length and the width of the terrace, and the number of lamp colours.

The next k lines contain four numbers x_1, y_1, x_2, y_2 (0 \le x_1, x_2 \le n, 0 \le y_1, y_2 \le m), positions of the first and the second lamp of the i-th colour.

Output Specification

In a single line, output the number of nice rectangles.


Subtask Points Constraints
1 26 x_1 = y_1 = 0 for each lamp colour
2 12 n, m \le 10, k \le 1\,000
3 35 m \le 150
4 37 No additional constraints.

Sample Input 1

2 2 1
0 0 1 2

Sample Output 1


Explanation for Sample Output 1

The image shows all the nice rectangles from the first example.

Sample Input 2

3 3 0

Sample Output 2


Sample Input 3

3 3 5
0 0 0 0
0 0 1 3
0 0 3 1
1 3 3 1
1 3 3 1

Sample Output 3



There are no comments at the moment.