dreptunghiuri3

Dreptunghiuri3

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

Poveste şi cerinţă...

Fie un caroiaj cu $N$ linii şi $M$ coloane care formează $N*M$ căsuţe, cu valoarea $0$ în fiecare. Asupra caroiajului se efectuează $K$ operaţii de tipul:
 
* $adună(i{~1~}, j{~1~}, i{~2~}, j{~2~}, v)$ care are următorul efect: valorile din căsuţele dreptunghiului având colţul stânga jos în poziţia $(i{~1~}, j{~1~})$ şi colţul dreapta sus în poziţia $(i{~2~}, j{~2~})$ cresc cu valoarea $v$.
 
h2. Cerinţă
 
Calculaţi valoarea maximă care apare în căsuţe după efectuarea celor $K$ operaţii şi determinaţi numărul de căsuţe în care aceasta apare.

h2. Date de intrare

Fişierul de intrare $dreptunghiuri3.in$ ...

Fişierul de intrare $dreptunghiuri3.in$ conţine pe prima linie numerele naturale $N$, $M$ şi $K$ separate prin câte un spaţiu. Pe fiecare din următoarele $K$ linii se află argumentele unei operaţii separate prin câte un spaţiu: $i{~1~} j{~1~} i{~2~} j{~2~} v$.

h2. Date de ieşire

În fişierul de ieşire $dreptunghiuri3.out$ ...

Fişierul de ieşire $dreptunghiuri3.out$ va conţine pe prima linie două numere separate printr-un spaţiu: valoarea maximă din căsuţe şi numărul de căsuţe în care apare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 1 000 000 000$
* $1 ≤ K ≤ 1 000$
* $|v| ≤ 1 000 000$, unde $|v|$ este valoarea absolută a lui $v$
* Pentru $20%$ din teste $N, M, K ≤ 100$
* Pentru alte $30%$ din teste $N, M ≤ 2 000$

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 5 3
  1 1 2 2 1
  4 2 5 5 3
  2 2 4 4 2
| 5 3

|
h3. Explicaţie

...

Celulele $(4, 2)$, $(4, 3)$ şi $(4, 4)$ conţin toate valoarea $5$. Restul căsuţelor conţin valori strict mai mici.

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

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

5472