lcdr

LCDR

== include(page="template/taskheader" task_id="lcdr") ==

Poveste şi cerinţă...

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?

h2. Date de intrare

Fişierul de intrare $lcdr.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $lcdr.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. lcdr.in |_. lcdr.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|

h3. Explicaţie
 
...
 

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

5652