Fişierul intrare/ieşire:parcele2.in, parcele2.outSursăONIS 2015, Runda 3
AutorAlexandru IonitaAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 Ai, Xi, Yi, 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 acestui an. Copacii pot fi adaugati insa doar pe parcela din dreapta jos a regiunilor de interes si se va 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 trei numere intregi: Ai Xi Yi.
Pe urmatoarea linie se afla numarul Q, reprezentand numarul de query-uri. Pe fiecare dintre cele Q linii se afla patru 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 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.inparcele2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content