In this HackerEarth Submatrix Updates problem solution, You will be given a N x M matrix A of integers and K add operations to execute. An add operation adds a constant to all of the entries in a square sub-matrix of A and it is specified by 4 integers R, C, S, and D where R is the row number, C is the column number, S is the size of the sub-matrix and D is the constant to add to the entries. The entry at row R and column C is denoted by A[R][C]. The row and column numbers in a query corresponding to the upper-left corner of the square sub-matrix to update.

Your task it to print the matrix after applying all of the K add operations.


HackerEarth Submatrix Updates problem solution


HackerEarth Submatrix Updates problem solution.

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n, m, k;
int r, c, s;
long long d;

long long a[N][N];
long long lazy[N][N];

        
int main(void) {

    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    while(k--) {
        cin >> r >> c >> s >> d;
        r -= 1, c -= 1;
        for(int i = 0; i < s; i++) {
            lazy[i + r][c] += d;
            lazy[i + r][c + s] -= d;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(j - 1 >= 0) lazy[i][j] += lazy[i][j - 1];
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << (a[i][j] + lazy[i][j]) << " ";
        }
        cout << endl;
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;


const int MaxN = 1e3 + 13;

int a[MaxN][MaxN];
int n, m, k;
int up[MaxN][MaxN];

void add(int x, int y, int xx, int yy,int delta)
{
    if(xx > n)
        xx = n;

    if(yy > m)
        yy = m;

    up[x][y] += delta;
    up[xx + 1][y] -= delta;
    up[x][yy + 1] -= delta;
    up[xx + 1][yy + 1] += delta;
}

void push()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            up[i][j] = up[i][j] + up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1];
            a[i][j] += up[i][j];
        }
}

main()
{

    cin >> n >> m >> k;

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];

    for(int i = 1; i <= k; ++i)
    {
        int x, y, d, c;
        cin >> x >> y >> d >> c;
        add(x, y, x + d - 1, y + d - 1, c);
    }
    push();
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}