Hide

Problem G
Veggspjöld

/problems/iceland.veggspjold/file/statement/en/img-0001.jpg
Posters

Hrolleifur is quite the cinephile and collects all kinds of paraphernalia related to movies. One of the things he has done is collect posters that advertise movies. He makes sure to own at least one poster for each movie, which he then glues to the wall in his room.

Now Hrolleifur has collected posters for years and is getting close to the point where they cover his wall completely. After Hrolleifur has glued a poster to the wall it will not move. Unfortunately Hrolleifur hasn’t always been careful enough when gluing them to the wall and thus some of the posters overlap even though the wall isn’t fully covered.

Hrolleifurs’ wall and all his posters are rectangular. Even though Hrolleifur hasn’t always been careful to make sure the posters don’t overlap, he always makes sure they aren’t crooked, with each edge aligned parallel to the corresponding edge of the wall.

How much area is left unused?

\includegraphics[width=0.5\textwidth ]{sample2}
Figure 1: Sample 2

Input

The first line contains three integers $b, h$ and $n$ where $b$ and $h$ are the width and height of Hrolleifs’ wall and $n$ is the number of posters he’s glued up. It will always hold that $1 \leq b, h \leq 10^9$ and $1 \leq n \leq 10^5$. Next there are $n$ lines with four integers each, $0 \leq x_1 < x_2 \leq b$ and $0 \leq y_1 < y_2 \leq h$ where $x_1$, $x_2$ are the distances of the left and right edge of the poster from the left edge of the wall and $y_1, y_2$ are the distances of the bottom and top edge of the poster from the ceiling. All units are in centimeters.

Output

Print a single integer, the area of the part of the wall not covered with any posters in square centimeters.

Scoring

Group

Points

Constraints

1

10

$1 \leq b, h \leq 200$, $0 \leq n \leq 50$, no two posters overlap

2

15

$1 \leq b, h \leq 200$, $0 \leq n \leq 50$, at most two posters overlap in any given location

3

20

$1 \leq b, h \leq 200$, $1 \leq n \leq 1\, 000$

4

25

$1 \leq b, h \leq 2\, 000$, $1 \leq n \leq 1\, 000$

5

25

$1 \leq n \leq 1\, 000$

6

5

No further constraints

Sample Input 1 Sample Output 1
10 10 5
0 2 0 2
3 5 1 3
9 10 0 10
1 2 4 5
3 7 6 8
73
Sample Input 2 Sample Output 2
5 7 3
0 2 0 3
1 4 2 5
3 5 4 7
16
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Authors
Arnar Bjarni Arnarson and Sigurður Jens Albertsson
Source Forritunarkeppni Framhaldsskólanna 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in