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 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 POZ1 si LUNG1 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 POZi si DLUNGi, 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: LUNGi = LUNGi - 1 + DLUNGi.

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

drept2.indrept2.out
5 6 2 3
1 5
1 -2
1 -1
1 -1
3 2
2 1
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?

remote content