Fişierul intrare/ieşire:rombulum.in, rombulum.outSursăONIS 2014, Runda Finala
AutorPaul DiacAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rombulum

Fie o matrice cu N linii si N coloane cu numere intregi cu toate valorile initiale egale cu 0. Pe aceasta matrice se relizeaza o serie de Q update-uri definite prin x, y, lat, val; cu seminificatia: Elementele care se afla in interiorul rombului cu colturile (x - lat, y), (x, y + lat), (x + lat, y), (x, y - lat) se modifica adaugand valoarea val.

De exemplu pornind de la matricea initiala 7 × 7 cu toate elementele 0, printr-un update (4, 5, 2, 1) ajungem la matricea:

\|1234567
-+-------
1|0000000
2|0000100
3|0001110
4|0011111
5|0001110
6|0000100
7|0000000

Pentru a rezolva problema trebuie sa determinati doua cele mai mari valori din matrice, dupa update-uri, dar si numarul de aparitii ale acestor doua valori.

Date de intrare

Fişierul de intrare rombulum.in contine pe prima linie numarul de teste T.
Fiecare test este descris pe prima linie prin doua numere N si Q, numarul de linii si coloane ale matricii si numarul de update-uri. Fiecare din urmatoarele Q linii contine 4 numere x y lat val care descriu update-ul.

Date de ieşire

În fişierul de ieşire rombulum.out trebuie sa afisati pentru fiecare test 4 numere v1 f1 v2 f2 cu seminificatia:

v1 = valoarea maxima din matrice
f1 = numarul de aparitii ale lui v1
v2 = a doua cea mai mare valoare (vor exista cel putin doua valori distincte)
f2 = numarul de aparatii ale lui 2

Restricţii

  • T ≤ 16
  • 1 ≤ N ≤ 250
  • 1 ≤ Q ≤ 50000
  • 0 ≤ val ≤ 1000 pentru orice update
  • orice update contine toate elementele in interiorul matricii : x - lat, x + lat, y - lat, y + lat vor apartie intervalului [1, N].

Exemplu

rombulum.inrombulum.out
2
8 2
4 4 3 2
6 6 2 3
10 7
8 2 1 616
2 6 1 796
3 3 2 397
3 6 1 622
5 4 2 774
5 2 1 502
7 8 1 92
5 5 3 8
1673 1 1418 2

Explicaţie

Pentru primul test matricea care se formeaza este urmatoarea:

\|12345678
-+--------
1|00020000
2|00222000
3|02222200
4|22222520
5|02225530
6|00255333
7|00023330
8|00000300

Cea mai mare valoare este 5 cu 5 aparitii iar a doua cea mai mare valoare este 3 cu 8 aparitii.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content