Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | parcele2.in, parcele2.out | Sursă | ONIS 2015, Runda 3 |
| Autor | Alexandru Ionita | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Parcele2
O suprafata de pamant este impartita in NxM parcele de teren. Pe aceasta suprafata au fost plantati pe parcele de coordonate cunoscute un numar P de copaci, fiecare intr-un anumit an calendaristic. Astfel pentru un copac se cunosc valorile A~i~, X i, Y i), cu 1 ≤ i ≤ P, unde Ai este anul in care a fost plantat copacul i iar Xi si Yi sunt coordonatele parcelei pe care a fost plantat. Se stie ca fiecare copac isi mareste inaltimea de K ori in fiecare an. Astfel, in anul in care a fost plantat, copacul are inaltimea 1, iar in al doilea an k, in al treilea k2 etc.
Definim o regiune ca fiind o suprafata de teren dreptunghiulara cu laturile paralele cu cele ale terenului, specificata prin parcelele stanga-sus si dreapta-jos: (XS, YS), (XD, YD).
O regiune este considerata "frumoasa", daca pentru fiecare inaltime H exista un numar par de copaci cu acea inaltime.
In anul 2015 proprietarul a descoperit o metoda ingenioasa a adauga noi copaci de orice inaltime. Folosind aceasta metoda el este interesat sa "infrumuseteze" pe rand Q regiuni ale suprafetei, pe parcursul anului. Copacii pot fi adaugati insa doar pe parcela din dreapta jos a regiunilor de interes si se vor planta un numar minim de copaci. Dupa ce regiunea a devenit frumoasa, copacii plantati raman pe parcela respectiva.
Date de intrare
Pe prima linie a fisierului de intrare parcele2.in se va afla T, reprezentand numarul de teste.
In cadrul unui test, pe prima linie se vor afisa numerele N, M si K, reprezentand dimensiunea terenului si coeficientul de crestere a copacilor intr-un an.
Pe urmatoarea linie urmeaza numarul P, reprezentand numarul de copaci plantati initial pe parcela. Pe fiecare dintre urmatoarele P linii se afla 3 numere intregi: Ai Xi Yi.
Pe urmatoarea linie se afla un numarul Q, reprezentand numarul de query-uri. Pe fiecare dintre cele Q linii se afla 4 numere intregi, reprezentand colturile din stanga sus si dreapta jos ale unei regiuni pe care proprietarul doreste sa o "infrumuseteze".
Date de ieşire
Fişierul de ieşire parcele2.out contine pentru fiecare test i, Qi linii, 1≤i≤T. Pe fiecare linie, afisati un numar C, reprezentand numarul de copaci ce trebuie plantati de proprietar, urmat de o succesiune de inaltimi H, cu semnificatia ca acesta planteaza cate un copac de fiecare inaltime specificata. Pentru ca acestea pot fi numere foarte mari, afisati-le modulo 666013. Inaltimile pot fi afisate in orice ordine.
Restricţii
- 1 ≤ T ≤ 10
- 1955 ≤ Ai ≤ 2015
- 1 ≤ N, M ≤ 1000
- 1 ≤ Xi ≤ N si 1 ≤ Yi ≤ M
- 1 ≤ K ≤ 100
- 1 ≤ P + Q ≤ 2000
Exemplu
| parcele2.in | parcele2.out |
|---|---|
| 1 3 4 3 4 2013 1 2 2013 1 2 2011 2 2 2014 1 3 3 1 1 2 3 2 2 3 4 1 2 2 4 | 2 3 81 1 3 0 |
Explicaţie
La inceput sunt patru copaci plantati pe teren ca in figura alaturata:
Proprietarul doreste sa afle ce copaci trebuie sa mai planteze pe regiunea ((1, 1)(2, 3)) pentru ca aceasta sa devina frumoasa. El planteaza astfel un copac de inaltime 81 si unul de inaltime 3 pe parcele (2, 3).
Apoi, acesta doreste sa "infrumuseteze" regiunea ((2, 2)(3, 4)) si va planta un copac pe parcela (3, 4), de inaltime 3.
In final, pentru a "infrumuseta" regiunea ((1, 2)(2, 4)), el nu trebuie sa planteze niciun copac.
