drept2

Drept 2

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

h2. Restrictii si precizari

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

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

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

| 5 6 2 3
1 5
1 -2
1 -1
1 -1
3 2
2 1
| 3

|
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") ==

1792