| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 34 | 8 | 8 | 42.105% |
Zbog globalnog zatopljenja sve češće ljeti viđamo velike požare. Zaštićena šuma „Matričin lug” smatra se osobito rizičnom pa vatrogasci mole da napišeš program koji će predvidjeti širenje nekoliko požara u toj šumi.
Matričin lug poznat je po tome što se može vizualizirati kao tablica s N redaka i M stupaca. Ono što je manje poznato je da požari u toj šumi uvijek počinju u obliku kvadrata ili romba. Označimo polje u x-tom retku i y-tom stupcu Matričinog luga oznakom (x, y).
Požar koji počinje u obliku kvadrata sa središtem u (Xi, Yi) raširenosti Ai nalazi se na svim poljima (x, y) za koja vrijedi max(|Xi - x|, |Yi - y|) < Ai.
Požar koji počinje u obliku romba sa središtem u (Xi, Yi) raširenosti Ai obuhvaća sva polja (x, y) za koja vrijedi |Xi - x| + |Yi - y| < Ai.
Bez obzira na oblik, obje vrste požara šire se na isti način. Ako u jednoj minuti šuma na nekom polju gori, onda će u sljedećoj minuti goriti i šuma na svim poljima direktno susjednima tom polju. Moguće je da će se početni požari preklapati u nekim poljima šume.
U nultoj minuti gorit će samo područja u kojima počinju požari. Šuma gori jako sporo pa se niti jedno opožareno polje nikada neće ugasiti. Vatrogasce za Q trenutaka zanima koliko će polja šume goriti u minuti Ti.
U prvom su retku dva prirodna broja N i M (1 ≤ N, M ≤ 2000), brojevi iz teksta zadatka.
U sljedećem retku su tri cijela broja: K, R i Q (0 ≤ K, R ≤ 2000, 1 ≤ Q ≤ 2000), redom broj kvadratastih požara, broj rombastih požara i broj upita iz teksta zadatka.
U sljedećih K redaka su po tri prirodna broja Xi, Yi i Ai (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M, 1 ≤ Ai ≤ 2000), redak i stupac središta te raširenost i-tog požara koji započinje u obliku kvadrata.
U sljedećih R redaka su po tri prirodna broja Xi, Yi i Ai (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M, 1 ≤ Ai ≤ 2000), redak i stupac središta te raširenost i-tog požara koji započinje u obliku romba.
U sljedećih Q redaka je po jedan cijeli broj Ti (0 ≤ Ti ≤ 2000) koji odgovara i-tom upitu vatrogasaca.
Potrebno je ispisati Q redaka. U i-tom retku treba ispisati koliko polja šume će gorjeti u minuti Ti.
8 10 1 1 3 2 3 2 5 5 2 0 1 2
14 29 41
5 5 1 1 4 4 4 2 3 3 2 0 1 2 3
11 18 24 25
6 6 1 1 3 1 1 3 6 6 3 0 1 2
15 25 34
Opis prvog probnog primjera: U nultoj minuti požar će se nalaziti samo na crvenim poljima, kojih je 9+5=14. U sljedećoj minuti gorjet će i narančasta polja pa će ukupno gorjeti 14+15=29 polja, a u minuti nakon i žuta polja će gorjeti što je ukupno 29+12=41 polje.
ΔΔΔΔΔΔ.... ΔΔΔΔΔΔ.... ΔΔΔΔΔΔ.... ΔΔΔΔΔΔΔ... .ΔΔΔΔΔΔΔ.. ..ΔΔΔΔΔ... ...ΔΔΔ.... ....Δ.....