Drept2

Drept 2

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

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 $drept.out$ va contine o singura linie pe care veti scrie numarul de dreptunghiuri care respecta conditiile din enunt.

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 |
| 5 6 2 3
1 5

1 3
1 2
1 1
3 3
2 4

1 -2
1 -1
1 -1
3 2
2 1

| 3
|

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

1792