Fişierul intrare/ieşire:	drept2.in, drept2.out	Sursă	Lot Ploiesti 2006
Autor	Cosmin Silvestru Negruseri, Dan-Ionut Fechete	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.55 sec	Limită de memorie	54096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Drept 2

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.

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.

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₁ si LUNG₁ 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.

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.

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.

Exemplu

Explicatie

Cele 3 dreptunghiuri au colturile stanga-sus / dreapta-jos:
(1,1) / (3,2)
(1,1) / (2,3)
(5,3) / (6,5)

Cum se trimit solutii?