rombulum

Rombulum

== include(page="template/taskheader" task_id="rombulum") ==

Fie o matrice cu N linii si N coloane cu numere intregi cu toate valorile initiale elgale 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 patratului cu colturile (x - lat, y), (x, y + lat), (x + lat, y), (x, y - lat) se modifica adaugand valoarea val.

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 x 7 cu toate elementele 0, printr-un update (4, 5, 2, 7) ajungem la matricea:

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

$\|1234567$
$-+-------$

$6|0000100$
$7|0000000$

Pentru a rezolva problema trebuie sa determinati cele mai frecvente valori din matrice dupa o ce se realizeaza o serie de update-uri de tipul descris.

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.

h2. 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 contin 4 numere *x y lat val* care descriu update-ul.

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.

h2. Date de ieşire

În fişierul de ieşire $rombulum.out$ trebuie sa afisati pentru fiecare test doua din cele mai frecvente valori care se afla in matrice la final. Mai exact trebuie sa afisati 4 numere *v1 f1 v2 f2* cu seminificatia:

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

v1 = cea mai frecventa valoarea
f1 = numarul de aparitii ale lui v1
v2 = a doua cea mai frecventa valoarea
f2 = numarul de aparatii ale lui 2

$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$

h2. Restricţii
* T ≤ 16
* 1 ≤ N ≤ 250
* 1 ≤ Q ≤ 50000

* val ≤ 1000 pentru orice update
* orice update contine toate elementele in interiorul matricii : x - lat, x + lat, y - lat, y + lat for apartie [1, N].

* 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]$.

h2. Exemplu
table(example). |_. rombulum.in |_. rombulum.out |

| 6

| 2

  8 2
  4 4 3 2
 6 6 2 3

 5 2 1 502
 7 8 1 92
| 5 5 3 8

  5 5 3 8

  1673 1 1418 2

|
h3. 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.
 

== include(page="template/taskfooter" task_id="rombulum") ==

9907