Fişierul intrare/ieşire:	tnia.in, tnia.out	Sursă	OJI 2018, Clasa a 9-a
Autor	Eugenie Daniel Posdarascu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	0.35 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tnia

Se dă o matrice binară cu n coloane şi m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m. Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1,h[i]] şi în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordine crescătoare (h[i-1] ≤ h[i], 1 ≤ i ≤ n). 

Cerinţă

Să se răspundă la q întrebări de forma: dându-se numerele A, B, C, D se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colţul stânga-jos în coloana A şi linia B, iar colţul dreapta-sus în coloana C şi linia D.

Date de intrare

Fişierul de intrare este tnia.in.

• pe prima linie se găsesc două numere naturale n şi m despărţite printr-un spaţiu, cu semnificaţia de mai sus;
• pe a doua linie sunt cele n elemente h[i] ale vectorului despărţite prin câte un spaţiu;
• pe a treia linie este un număr natural q ce reprezintă numărul de întrebări;
• pe următoarele q linii se găsesc câte 4 numere A, B, C, D cu semnificaţia de mai sus, despărţite prin câte un spaţiu

Date de ieşire

Fişierul de ieşire tnia.out va conţine q linii reprezentând răspunsul pentru fiecare întrebare.

Restricţii

• 0 ≤ h[i] ≤ m, 1 ≤ n ≤ 100.000
• 1 ≤ q ≤ 100.000, 1 ≤ m ≤ 1.000.000.000
• Pentru 15 puncte: n, m, q ≤ 100
• Pentru alte 16 puncte: n, m, q ≤ 3.000
• Pentru alte 16 puncte: n ≤ 100.000, m ≤ 1.000.000.000, q ≤ 100
• Conform regulamentului OJI, se vor acorda 10 puncte din oficiu (cand adaugam testele facem specificatii in paranteza cum se obtin).

Exemplu

Cum se trimit solutii?