== include(page="template/taskheader" task_id="drept2") ==
Fie $X$ o matrice cu $M$ coloane (numerotate de la $1$ la $M$) si $N$ linii (numerotate de la $1$ la $N$) cu componente din multimea ${0, 1}$. Pe fiecare linie a matricei se afla o singura secventa (eventual vida) formata din elemente egale cu 1, secventa identificata prin pozitia de inceput (indicele coloanei pe care se afla primul 1 din secventa) si lungimea ei. Restul elementelor de pe linie sunt egale cu 0.
h2. Cerinta
Sa se determine numarul de dreptunghiuri cu dimensiunile $A$ si $B$, formate numai din $1$ care se afla in matricea $X$. Dreptunghiurile numarate au fie $A$ linii si $B$ coloane, fie $A$ coloane si $B$ linii.
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $drept2.in$ contine pe prima linie cele $4$ numere naturale separate prin cate un spatiu cu semnificatia din enunt, in ordinea $M N A B$.
Urmatoarele $N$ linii contin descrierea matricei $X$.
Pe linia a doua se afla 2 numere $POZ{~1~}$ si $LUNG{~1~}$ reprezentand pozitia de inceput si lungimea secventei de elemente egale cu $1$ de pe linia $1$ a matricei $X$.
Linia $i + 1$ ({$i ≥ 2$}) a fisierului contine doua numere $POZ{~i~}$ si $DLUNG{~i~}$, reprezentand pozitia de inceput a secventei de elemente egale cu $1$ de pe linia $i$ a matricei si lungimea secventei exprimata in functie de cea de pe linia precedenta. Lungimea se va calcula dupa urmatoarea formula: $LUNG{~i~} = LUNG{~i - 1~} + DLUNG{~i~}$.
...
h2. Date de iesire
Fisierul de iesire $drept2.out$ va contine o singura linie pe care veti scrie numarul de dreptunghiuri care respecta conditiile din enunt.
...
h2. Restrictii si precizari
h2. Restrictii
* $1 ≤ N, A, B ≤ 2 000 099$
* $1 ≤ M ≤ 5 000 099$
* $0 ≤ Lungimea unei secvente formata din elemente egale cu 1 ≤ M$
* Formatul de intrare a fost schimbat fata de cel din concurs pentru a micsora dimensiunea testelor.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. drept2.in |_. drept2.out |
| 5 6 2 3
1 5
1 -2
1 -1
1 -1
3 2
2 1
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
!problema/drept2?figura.jpg!
Cele $3$ dreptunghiuri au colturile stanga-sus / dreapta-jos:
$(1,1) / (3,2)$
$(1,1) / (2,3)$
$(5,3) / (6,5)$
...
== include(page="template/taskfooter" task_id="drept2") ==
