Iste každý už počul o rieke Ipeľ. Ak si myslíte, že sa jedná o nejakú riečku na juhu Slovenska, tak ste ne omyle. Totiž každý južan (vrátane mňa) si pamätá, ako sa veľtok Ipľu vylial. Záplavy zasiahli aj naše mesto a zničili v ňom bohatú infraštruktúru1.
V posledných rokoch je však obodbie sucha, a tak veľa ľudí zabúda na toto nebezpečenstvo. Túto zimu mi však istá nemnovaná osoba (Iľko) dala info, že Ipeľ sa vyleje. Ľadové kryhy, ktoré vzniknú pri výkyvoch teploty, totiž upchajú jeho koryto.
Keď teda vieme, že nastane katastrofa, musíme sa pripraviť. Vieme, že vysoké budovy v našom meste zastavia vodu. Máme mapu mesta, na ktorej sú tieto budovy vyznačené. Zaujíma nás, koľko územia ostane nezaplaveného.
Úloha
Svet si budeme predstavovať ako nekonečnú štvorcovú sieť. Nejaký obdĺžnikový kus tejto štvorcovej siete je naše mesto. Niektoré políčka v meste sú nezastavané (cesty, polia, …), na ostatných sú budovy. Každá budova zaberá presne jedno políčko. Zo všetkých strán mesta sa začne valiť voda. Voda zaplaví všetky políčka, kam sa vie dostať pohybom v 4 základných smeroch bez toho, aby prešla cez budovu. Zaujíma nás, koľko nezastavaných políčok ostane nezaplavených.
Formát vstupu
V prvom riadku vstupu sú tri celé čísla \(n, m\) a \(k\) (\(1 \leq n,m \leq 10 ^{18}\) a \(0 \leq k \leq 10^6\)): rozmery nášho mesta a počet budov v ňom.
Nasleduje \(k\) riadkov, \(i\)-ty z nich obsahuje dve celé čísla \(x_i, y_i\) – pozícu \(i\)-tej boudovy na mape. Presnejšie, \(i\)-ta budova sa nachádza v \(x_i\)-tom stĺpci a \(y_i\)-tom riadku obdĺžnika tvoriaceho naše mesto, číslujúc od \(0\). Platí teda \(0 \leq x_i < n\) a \(0 \leq y_i < m\). Možete predpokladať, že na každom políčku je najviac 1 budova.
Formát výstupu
Vypíšte jedno číslo – počet nezaplavených políčok mapy.
Hodnotenie
Pre jednotlivé sady testovacích vstupov platia nasledovné obmedzenia:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(n,m \leq\) | \(50\) | \(1\,000\) | \(1\,000\) | \(10 ^ {18}\) |
Príklady
Input:
3 3 4
2 1
0 1
1 0
1 2
Output:
1
Input:
7 5 17
1 0
1 1
1 2
1 3
1 4
2 0
3 0
3 2
3 3
3 4
4 0
4 4
5 0
5 1
5 2
5 3
5 4
Output:
0
Po zaplavení vyzerá mesto takto:
Dva semafory a štyri kruhové objazdy↩
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.