Hide

Problem G
Veggspjöld

/problems/iceland.veggspjold/file/statement/is/img-0001.jpg
Veggspjöld

Hrolleifur er mikill kvikmyndaáhugamaður og safnar allskyns munum tengdum kvikmyndum. Eitt af því sem hann hefur stundað er að safna veggspjöldum sem auglýsa kvikmyndirnar. Hann hefur gætt þess að eiga til að minnsta kosti eitt veggspjald fyrir hverja kvikmynd, sem hann límir síðan á vegginn í herberginu sínu.

Nú hefur Hrolleifur safnað veggspjöldunum í fjölda ára og nálgast að þau þekji vegginn hann fullkomlega. Eftir að Hrolleifur hefur límt veggspjald situr það fast á sínum stað. Því miður hefur Hrolleifur ekki alltaf verið nógu vandvirkur þegar hann límir þau á vegginn og því skarast sum veggspjöldin þó svo að veggurinn sé ekki fullþakinn.

Veggur Hrolleifs og öll veggspjöldin eru rétthyrnd. Þó svo að Hrolleifur hafi ekki alltaf gætt þess að láta veggspjöldin ekki skarast, hefur hann ávallt gætt þess að veggspjöldin snúi rétt, því er efri brún veggspjaldanna ávallt lárétt.

Hve stórt svæði af veggnum er enn ónotað?

\includegraphics[width=0.5\textwidth ]{sample2}
Figure 1: Sýnidæmi 2

Inntak

Fyrsta lína inniheldur þrjár heiltölur $b, h$ og $n$ þar sem $b$ og $h$ eru breidd og hæð vegg Hrolleifs og $n$ er fjöldi veggspjaldanna sem hann hefur límt á vegginn. Það gildir alltaf að $1 \leq b,h \leq 10^9$ og $1 \leq n \leq 10^5$. Næst fylgja $n$ línur með fjórum heiltölum hver, $0 \leq x_1 < x_2 \leq b$ og $0 \leq y_1 < y_2 \leq h$ þar sem $x_1$, $x_2$ eru fjarlægðir vinstri og hægri brúnar veggspjaldsins frá vinstri hlið veggjarins og $y_1$, $y_2$ eru fjarlægðir neðri og efri brúnar veggspjaldsins frá loftinu. Allar einingar eru í sentímetrum.

Úttak

Skrifaðu út eina heiltölu, flatarmál þess hluta veggjarins sem er ekki þakið neinu veggspjaldi í fersentímetrum.

Stigagjöf

Hópur

Stig

Takmarkanir

1

10

$1 \leq b, h \leq 200$, $0 \leq n \leq 50$, engin tvö veggspjöld skarast

2

15

$1 \leq b, h \leq 200$, $0 \leq n \leq 50$, mesta lagi tvö veggspjöld skarast á sama stað

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

Engar frekari takmarkanir

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

Please log in to submit a solution to this problem

Log in