Lacul

Time limit: 0.2s Memory limit: 64MB Input: lacul.in Output: lacul.out

Lacul codrilor albastru
Nuferi galbeni îl încarcă;
Tresărind în cercuri albe
El cutremură o barcă.
Mihai Eminescu, Lacul

Cerință

GrandPaPà, anticul și legendarul păzitor al lacului din poezia Eminesciană "Lacul", a descoperit într-o dimineață kk nuferi galbeni patrați pe suprafața apei. Suprafața apei poate fi codificată ca o matrice de nn linii si mm coloane.

Nufărul cu identificatorul ii (1iK1 \le i \le K), latura latlat și colțurile în regiunile (li,ci)(l_i,c_i), (li,ci+lat1)(l_i,c_i+lat-1), (li+lat1,ci)(l_i+lat-1,c_i) și (li+lat1,ci+lat1)(l_i+lat-1,c_i+lat-1) va acoperi toată submatricea corespunzătoare cu valoarea ii. Se garantează că nu există doi nuferi care să se suprapună, însă doi nuferi se pot atinge pe margini.

Dacă o regiune nu este acoperită de nici un nufăr, atunci elementul aferent din matrice va avea valoarea 00.

Această problemă are mai multe cerințe. În funcție de numărul cerinței CC (1c31 \le c \le 3), va trebui să afișați:

  • Dacă c=1c=1, afișați 33 numere, lmax, numar și id — latura maximă a unui nufăr, numărul de nuferi cu latura maximă, respectiv identificatorul minim al unui nufăr cu latura maximă.
  • Dacă c=2c=2, GrandPaPà va face QQ poze la lac, a ii-a poza cuprinzând submatricea cu colțurile de stânga-sus și dreapta-jos în regiunile (l1i,c1i)(l_{1_i},c_{1_i}), respectiv (l2i,c2i)(l_{2_i},c_{2_i}). Pentru fiecare poză, afișați numărul de nuferi incluși complet în submatricea fotografiată.
  • Dacă c=3c=3, similar cu cerința 22, GrandPaPà va face QQ poze la lac. Pentru fiecare poză, afișați numărul de nuferi incluși parțial sau complet în submatricea fotografiată.

Date de intrare

Pe prima linie a fișierului de intrare lacul.in se va afla numărul cerinței cc (1c31 \le c \le 3).

Pe a doua linie se vor afla trei numere nn, mm și kk, (1n,m1001 \le n,m \le 100, 1knm1 \le k \le n \cdot m) — dimensiunile matricei, respectiv numărul de nuferi.

Pe fiecare dintre următoarele nn linii se vor afla câte mm numere, elementele matricei (0ai,jk0 \le a_{i,j} \le k).

Dacă c=2c=2 sau c=3c=3, pe a n+3n+3-a linie din fișierul de intrare se va afla qq (1q100.0001 \le q \le 100.000) — numărul de poze.

Pe următoarele qq linii se vor afla coordonatele colțurilor din stânga-sus, respectiv dreapta-jos a pozelor
(1l1l2n1 \le l_1 \le l_2 \le n, 1c1c2m1 \le c_1 \le c_2 \le m).

Date de ieșire

Dacă c=1c=1, afișați în fișierul de ieșire lacul.out 33 numere, latura maximă a unui nufăr, numărul de nuferi cu latura maximă, respectiv identificatorul minim al unui nufăr cu latura maximă.

Dacă c=2c=2, afișați, pentru fiecare dintre cele qq poze din fișierul de intrare, numărul de nuferi incluși complet în submatricea fotografiată.

Dacă c=3c=3, afișați, pentru fiecare dintre cele qq poze din fișierul de intrare, numărul de nuferi incluși parțial sau complet în submatricea fotografiată.

Restricții și precizări

  • Pentru 20 de puncte, c=1c=1;
  • Pentru 40 de puncte, c=2c=2;
  • Pentru restul de 40 de puncte, c=3c=3.
  • Pentru câte 10 puncte la fiecare dintre cerințele c=2c=2 și c=3c=3, toți nuferii au latura egală cu 11;
  • Pentru câte 20 puncte la fiecare dintre cerințele c=2c=2 și c=3c=3, k100k \le 100;

Exemplul 1

lacul.in

1
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0

lacul.out

4 2 5

Explicație

Pentru primul exemplu, există 22 nuferi cu latura maximă lmax=4lmax=4. Aceștia au identificatoarele 55, respectiv 77, dintre care 55 este cel mai mic.

Exemplul 2

lacul.in

2
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
4
1 1 9 10
2 1 5 9
5 4 6 9
1 2 8 8

lacul.out

7
2
1
3

Explicație

Pentru exemplele 22 și 33, Cele patru poze suprind următoarele submatrici:

  • Toți cei k=7k=7 nuferi sunt incluși complet în prima poză.
  • Nuferii cu identificatoarele 22 și 33 sunt incluși complet în a doua poză.
  • Nufărul 66 este singurul nufăr inclus complet în a treia poză.
  • Nuferii 11, 33 și 44 sunt incluși complet în a patra poză.

Exemplul 3

lacul.in

3
9 10 7
0 0 0 0 1 1 0 0 0 0
2 2 0 0 1 1 7 7 7 7
2 2 0 0 0 0 7 7 7 7
0 4 4 4 3 0 7 7 7 7
0 4 4 4 0 0 7 7 7 7
0 4 4 4 5 5 5 5 6 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
0 0 0 0 5 5 5 5 0 0
4
1 1 9 10
2 1 5 9
5 4 6 9
1 2 8 8

lacul.out

7
5
4
6

Explicație

  • Toți cei k=7k=7 nuferi sunt incluși complet în prima poză.
  • Nuferii cu identificatoarele 22 și 33 sunt incluși complet în a doua poză. Nuferii cu identificatoarele 11, 44 și 77 sunt incluși doar parțial.
  • Nufărul 66 este singurul nufăr inclus complet în a treia poză. Nuferii 44, 55 și 77 sunt incluși doar parțial.
  • Nuferii 11, 33 și 44 sunt incluși complet în a patra poză. Nuferii 22, 55 și 77 sunt incluși doar parțial.

Log in or sign up to be able to send submissions!