== include(page="template/taskheader" task_id="drept2") ==
Poveste si cerinta...
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.
h2. Date de intrare
...
Fisierul de intrare $drept.in$ contine pe prima linie cele $4$ numere naturale separate prin cate un spatiu cu semnificatia din enunt, in ordinea $M N A B$. Pe fiecare dintre urmatoarele $N$ linii se afla cate doua numere naturale separate prin spatiu, descriind matricea $X$. Mai exact linia $i$ a fisierului se afla pozitia de inceput si lungimea secventei de elemente egale cu $1$ de pe linia $i - 1$ a matricei $X$.
h2. Date de iesire
...
Fisierul de iesire $drept.out$ va contine o singura linie pe care veti scrie numarul de dreptunghiuri care respecta conditiile din enunt.
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$
h2. Exemplu
table(example). |_. drept2.in |_. drept2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4
| 3
|
h3. Explicatie
...
!problema/drept2?figura.jpg
Cele $3$ dreptunghiuri au colţurile stânga-sus/dreapta-jos:
$(1,1)/(3,2)$
$(1,1)/(2,3)$
$(5,3)/(6,5)$
== include(page="template/taskfooter" task_id="drept2") ==
