Finále

E: Tání ledovců

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Na ledovci u severního pólu žijí skřítci, kteří vyrábějí vánoční dárky. Bohužel v důsledku globálního oteplování nám ledovec taje. Kolik dárečků ještě skřítci stihnou vyrobit?

Ledovec je na začátku čtvercový, složený z mřížky N×N políček. Na některých políčkách jsou iglú skřítků. V každém iglú vyrobí skřítci každý večer jeden dárek. Každý den ráno (tedy před výrobou dárků) vždy roztaje jedno políčko ledovce (a zničí iglú na tomto políčku, pokud tam nějaké bylo). Pokud se tak ledovec rozdělil na více částí, které se nedotýkají, tak se všechny části kromě nejmenší potopí. Potopí se i se všemi iglú, které na nich stojí; tyto iglú přestanou vyrábět dárky. Dvě políčka se dotýkají, pokud mají společný roh nebo hranu (tj. max(|X1 - X2|, |Y1 - Y2|) ≤ 1). Velikost části ledovce je počet (neroztátých) políček, ze kterých se skládá. Chceme vědět, jaký bude celkový počet vyrobených dárků na konci R-tého dne.

Můžete předpokládat následující:

  • Vždy, když se ledovec rozdělí na víc částí, bude existovat jednoznačná nejmenší část.
  • Na každém políčku je nejvýše jedno iglú.
  • Nikdy neroztaje políčko, které už předtím roztálo nebo se potopilo.

Tvar vstupu

Na prvním řádku je číslo T - počet úloh, které máte vyřešit.
Pro každý úkol jsou na prvním řádku tři čísla oddělené mezerou: N - velikost strany ledovce, K - počet iglú, R - počet dní.
Následuje K řádků, každý z nich obsahuje dvě čísla X a Y popisující souřadnice jednoho z iglú. Souřadnice počítáme od 1 do N, levý horní roh je (1, 1).
Následuje R řádků, i-tý z nich obsahuje dvě čísla Xi a Yi popisující souřadnice políčka, které roztaje ráno i-tého dne.

Tvar výstupu

Vypište jediné číslo - celkový počet dárků, které skřítci vyrobí do konce R-tého dne. Pozor: Řešení se nemusí vejít do 32-bitového čísla (int v C++), použijte 64-bitové (long long int v C++).

Lehká verze

  • T ≤ 10
  • N ≤ 50
  • K ≤ 1 000
  • R ≤ 1 000

Těžká verze

  • T ≤ 10
  • N ≤ 500
  • K ≤ 100 000
  • R ≤ 50 000

Ukázkový vstup

2
4 5 5
1 1
4 1
1 4
4 4
1 2
2 1
2 2
2 3
2 4
1 2
4 5 6
1 1
4 1
1 4
4 4
1 2
2 1
2 2
1 3
3 3
4 3
2 3

Ukázkový výstup

19
27

Vysvětlení ukázkového vstupu a výstupu

V prvním vstupu se ledovec poprvé rozpadne čtvrtý den a zůstanou pouze políčka s x=1. Pátý den zůstane už jen políčko (1, 1).

V druhém vstupu se poslední den ledovec rozpadne na tři části, z nichž zůstane ta, která sestává z políček (1, 1) a (1, 2). Na ní jsou dvě iglú, takže stačí ještě ten večer vyrobit dva dárky.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)