Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-29 17:07:08.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:drept2.in, drept2.outSursăLot Ploiesti 2006
AutorCosmin Silvestru Negruseri, Dan-Ionut FecheteAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.55 secLimită de memorie54096 kbytes
Scorul tăuN/ADificultateN/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 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.

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.

Restrictii

  • 1 ≤ N, A, B ≤ 2 000 099
  • 1 ≤ M ≤ 5 000 099
  • 0 ≤ Lungimea unei secvente formata din elemente egale cu 1 ≤ M

Exemplu

drept2.indrept2.out
5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4
3

Explicatie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?