acces

Acces

!problema/acces?p1.jpg!
p<>. În această matrice se pot face deplasări doar pe direcţiile Vest şi Nord în elemente egale cu $0$, deci din poziţia $(i, j)$ se poate ajunge doar într-una dintre poziţiile $(i, j-1)$ şi $(i-1, j)$, marcate cu $0$. În acest fel, pornind de la o anumită poziţie, prin deplasări succesive, pot fi accesate un anumit număr de elemente ale matricei egale cu $0$. De exemplu, în $fig. 1$, din poziţia $(2, 4)$ pot fi accesate $5$ componente egale cu $0$, iar din poziţia $(5, 4)$ pot fi accesate $14$ componente egale cu $0$.

 Trebuie să răspundeţi la $Q$ întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia $(i, j)?$”

 Trebuie să răspundeţi la $Q$ întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia $(i, j)$?”

h2. Cerinţă

h2. Date de ieşire

Fişierul $acces.out$ conţine $Q$ linii. Pe linia $p (1 ≤ p ≤ Q)$ se află un număr natural k ~p~ reprezentând răspunsul la cea de-a $p$-a întrebare.

Fişierul $acces.out$ conţine $Q$ linii. Pe linia $p (1 ≤ p ≤ Q)$ se află un număr natural $k$~$p$~ reprezentând răspunsul la cea de-a $p$-a întrebare.

h2. Restricţii

* $4 ≤ L, C ≤ 1000$

* $4 ≤ L, C ≤ 1 000$

* $3 ≤ Q ≤ 500 000$

* $Pentru orice întrebare i j se garantează că valoarea corespunzătoare din matrice este 0$
* $Pentru toate testele, dreptunghiurile formate din valori de 1 nu se învecinează$

* Pentru orice întrebare $i j$ se garantează că valoarea corespunzătoare din matrice este $0$
* Pentru toate testele, dreptunghiurile formate din valori de 1 nu se învecinează

h2. Exemplu

11
3
|Pentru prima întrebare, cele 5 componente egale cu 0 care pot fi accesate sunt cele din

poziţiile $(1, 1), (1, 2), (1, 3), (1, 4), (2, 4)$

poziţiile $(1, 1), (1, 2), (1, 3), (1, 4), (2, 4).$

|

h3. Explicaţie
 
...
 

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

5597