2D Difference Painting - Classic Problems | Repovive

CLS55. 2D Difference Painting

2s256 MB

Start with an $n \times m$ grid of zeros. Apply $q$ rectangle increments, then print the final grid.

\begin{array}{l} n \quad m \quad q \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad x \\ \vdots \end{array}

\begin{array}{cccc} g_{1,1} & g_{1,2} & \cdots & g_{1,m} \\ g_{2,1} & g_{2,2} & \cdots & g_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ g_{n,1} & g_{n,2} & \cdots & g_{n,m} \end{array}

Input

3 4 2
1 1 2 3 5
2 2 3 4 -2

Explanation

Applying both rectangle updates leaves the final grid shown by the sample output.

Output

5 5 5 0
5 3 3 -2
0 -2 -2 -2

Input

2 2 1
1 1 2 2 7

Explanation

The single update covers the entire grid, so every cell becomes 7.

Output

7 7
7 7

Input

Explanation

Each cell receives the sum of the updates whose rectangles include it.

Output

4 0 -2
0 1 -1
0 1 -1

Start with an $n \times m$ grid of zeros. Apply $q$ rectangle increments, then print the final grid.

\begin{array}{l} n \quad m \quad q \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad x \\ \vdots \end{array}

\begin{array}{cccc} g_{1,1} & g_{1,2} & \cdots & g_{1,m} \\ g_{2,1} & g_{2,2} & \cdots & g_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ g_{n,1} & g_{n,2} & \cdots & g_{n,m} \end{array}