Fişierul intrare/ieşire:tnia.in, tnia.outSursăOJI 2018, Clasa a 9-a
AutorEugenie Daniel PosdarascuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.7 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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 pentru exemplu.

Exemplu

tnia.intnia.outExplicaţie
5 10
2 3 7 8 10
5
1 1 5 10
2 5 4 7
3 2 3 6
3 8 3 10
3 2 3 10
30
6
5
0
6
Zona dreptunghiulară având colţul stânga-jos la coloana 1 şi linia 1 şi colţul dreapta-sus la coloana 5 şi linia 10 are suma elementelor 30.
Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt: 6, 5, 0 şi 6.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?