Diff2dArrays

#3903

Se dă o matrice A, formată din N linii și N coloane. Asupra unei submatrice cu colțul din stânga-sus aflat pe linia l1 și coloana c1, și colțul din dreapta-jos aflat pe linia l2 și coloana c2, se poate efectua operație de mărire a elementelor cu un număr întreg v. Afișați matricea A, după efectuarea a Q astfel de operații.

Date de intrare

  • pe prima linie se află variabila N, reprezentând numărul de linii și coloane.
  • pe următoarele N linii, câte N numere întregi, reprezentând elementele matricii.
  • pe cea de-a N + 1 se află variabila Q, reprezentând numărul de operații ce trebuie efectuate.
  • pe următoarele Q linii, 5 numere : l1, c1, l2, c2, v, reprezentând linia și coloana colțului din stânga-sus, respectiv linia și coloana colțului din dreapta-jos al unei submatrici, căreia îi vor fi mărite elementele cu numărul întreg v.

Date de ieșire

Programul va afișa pe ecran matricea după aplicarea tuturor celor Q operații de mărire.

Restricții și precizări

  • 1 ≤ N ≤ 500
  • 1 ≤ Q ≤ 200.000
  • 1 ≤ l1 ≤ l2 ≤ N
  • 1 ≤ c1 ≤ c2 ≤ N
  • -1.000 ≤ v ≤ 1.000
  • Elementele matricii A vor avea valori cuprinse între [-10.000, 10.000]

Exemplu

Intrare

4
3 6 3 3
0 5 2 10
-4 4 10 -1
4 -1 8 3
2
1 1 4 2 10
1 1 4 4 -5

Ieșire

8 11 -2 -2
5 10 -3 5
1 9 5 -6
9 4 3 -2

Explicație

În prima operație se adună valoarea 10, submatricii delimitată de liniile 1, 4 și coloanele 1, 2 obținând matricea:
13 16 3 3
10 15 2 10
6 14 10 -1
14 9 8 3

În cea de-a doua operație se adună valoarea -5, întregii matrici obținând:
8 11 -2 -2
5 10 -3 5
1 9 5 -6
9 4 3 -2

#include <bits/stdc++.h>

using namespace std;

int a[502][502], s[502][502];
int N, Q, l1, c1, l2, c2, v;

int main() {

    cin >> N;
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= N;j++) {
            cin >> a[i][j];
        }

    cin >> Q;
    while(Q--) {
        cin >> l1 >> c1 >> l2 >> c2 >> v;

        s[l1][c1] += v;
        s[l1][c2 + 1] -= v;
        s[l2 + 1][c1] -= v;
        s[l2 + 1][c2 + 1] += v;
    }

    for(int i = 1;i <= N;i++, cout << "\n")
        for(int j = 1;j <= N;j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            cout << a[i][j] + s[i][j] << " ";
        }
    
    return 0;
}
%d bloggers like this: