Fişierul intrare/ieşire:lcdr.in, lcdr.outSursăLot Sibiu 2011
AutorMarius Dumitran, Perticas CatalinAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

LCDR

Se dă o matrice de dimensiuni N*M. Toate elementele matricei au valoarea 0 sau 1. Vor exista Q întrebări de forma: există vreun dreptunghi cu L linii şi C coloane cu toate elementele egale cu 1 situat în întregime între liniile L1 şi L2 ale matricei, inclusiv L1 şi L2?

Date de intrare

Fisierul lcdr.in conţine pe prima linie numerele N, M şi Q cu semnificaţia din enunţ. Următoarele N linii vor conţine fiecare câte M numere cu valoarea 0 sau 1, fără spaţii între ele. Urmează Q linii cu câte patru numere fiecare: L, C, L1, L2 cu semnificaţia din enunţ.

Date de ieşire

Fişierul lcdr.out va conţine Q numere, câte unul pe linie reprezentând răspunsurile la întrebări.

Restricţii

  • 1 ≤ N, M ≤ 500
  • 1 ≤ Q ≤ 500 000
  • Pentru 30% din teste, Q ≤ 500.
  • Pentru alte 40% din teste, Q ≤ 200 000.

Exemplu

lcdr.inlcdr.out
4 5 5
00000
11100
01111
01100
3 2 2 4
4 3 1 4
1 3 1 2
1 2 4 4
1 3 4 4
1
0
1
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content