Header Ad

HackerEarth Submatrix Updates problem solution

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';
}
}

Post a Comment

0 Comments