| Fişierul intrare/ieşire: | rombulum.in, rombulum.out | Sursă | ONIS 2014, Runda Finala |
| Autor | Paul Diac | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | rombulum.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.
