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.
#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';
}
}
0 Comments