All Tracks Data Structures Arrays Multi-dimensional Problem

Submatrix Updates
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

You will be given a $$N\times 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 correspond 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.

Input:

The first line of input contains three numbers $$N, M, K$$ representing the number of rows, the number of columns and the number of add operations respectively. $$N$$ lines follow each containing $$M$$ space-separated integers. $$K$$ lines follow each containing four numbers $$R, C, S$$ and $$D$$ as described above.

Output:

Print the matrix after applying all of the $$K$$ add operations. The matrix should be printed on $$N$$ lines each containing $$M$$ space-separated integers.

Constraints:

  • $$1\le N,M,K\le 1000$$.
  • $$1\le R\le N$$, $$1\le C\le M$$, $$1\le S\le min(N,M)$$ and $$-10^6\le D\le 10^6$$.
  • $$-10^6\le A[i][j]\le 10^6$$ for $$1\le i\le N$$ and $$1\le j\le M$$.
SAMPLE INPUT
4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2 3 2 5
3 2 2 -3
SAMPLE OUTPUT
1 2 3 4 
5 6 12 13 
9 7 13 17 
13 11 12 16 
Explanation

Take the entry $$A[3][3]=11$$. This entry is affected by both updates: we first add $$5$$ to it and then we subtract $$3$$ from it so the entry becomes $$A[3][3]=13$$ at the end.

Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

International Women's Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications