E - Paint Drop Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、縦 H マス、横 W マスのグリッド状のキャンバスでペイントゲームをしています。上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。

マス (i, j) には、スコア A_{i,j} が設定されています。最初、すべてのマスはペイントされていません。

高橋君はこれから Q 回、キャンバスにペイントを落とします。

t 回目のペイントでは、マス (R_t, C_t) を中心として、マンハッタン距離が D_t 以下であるすべてのキャンバス上のマスがペイントされます。

つまり、1 \leq i \leq H かつ 1 \leq j \leq W を満たすマス (i, j) のうち、

|i - R_t| + |j - C_t| \leq D_t

を満たすすべてのマスがペイントされます。

まだペイントされていないマスが新たにペイントされたとき、高橋君はそのマスのスコアを獲得します。すでにペイントされているマスに再びペイントが届いてもスコアは獲得できません。

各ペイントについて、そのペイントで高橋君が新たに獲得したスコアの総和を求めてください。

制約

  • 1 \leq H \leq 2 \times 10^5
  • 1 \leq W \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • H \times W \leq 4 \times 10^6
  • H \times Q \leq 4 \times 10^6
  • H + Q \leq 2 \times 10^5
  • 0 \leq A_{i,j} \leq 10^9
  • 1 \leq R_t \leq H
  • 1 \leq C_t \leq W
  • 0 \leq D_t \leq H + W
  • 入力はすべて整数である

入力

H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
Q
R_1 C_1 D_1
R_2 C_2 D_2
\vdots
R_Q C_Q D_Q
  • 1 行目には、キャンバスの縦のマス数 H と横のマス数 W がスペース区切りで与えられる。
  • 続く H 行のうち i 行目には、スコア A_{i,1}, A_{i,2}, \ldots, A_{i,W} がスペース区切りで与えられる。
  • 続く 1 行には、ペイントの回数 Q が与えられる。
  • 続く Q 行のうち t 行目には、t 回目のペイントの中心の行 R_t、列 C_t、届く距離 D_t がスペース区切りで与えられる。

出力

Q 行出力せよ。

t 行目には、t 回目のペイントで高橋君が新たに獲得したスコアの総和を出力せよ。

入力例 1

3 4
1 2 3 4
5 6 7 8
9 10 11 12
4
2 2 1
1 4 0
3 1 2
2 3 7

出力例 1

30
4
21
23

入力例 2

2 5
0 5 0 7 1
3 0 4 0 2
5
1 1 0
1 3 1
2 5 3
2 2 0
1 5 0

出力例 2

0
16
3
0
0

入力例 3

5 7
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8
3 4 2
1 1 3
5 7 1
2 6 4
4 2 0
5 1 5
1 7 0
3 3 10

出力例 3

52
30
13
46
6
18
0
0

入力例 4

8 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
12
4 5 3
1 10 2
8 1 4
3 7 0
6 6 5
2 2 1
7 9 3
1 1 18
8 10 0
5 3 2
4 10 6
8 5 8

出力例 4

875
96
885
0
1121
60
80
123
0
0
0
0

入力例 5

1 1
1000000000
4
1 1 0
1 1 1
1 1 2
1 1 0

出力例 5

1000000000
0
0
0

Score : 466 pts

Problem Statement

Takahashi is playing a paint game on a grid canvas with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j).

Cell (i, j) has a score A_{i,j} assigned to it. Initially, no cells are painted.

Takahashi will drop paint onto the canvas Q times.

In the t-th paint drop, all cells on the canvas whose Manhattan distance from cell (R_t, C_t) is at most D_t are painted.

In other words, among all cells (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, all cells satisfying

|i - R_t| + |j - C_t| \leq D_t

are painted.

When a cell that has not yet been painted becomes newly painted, Takahashi earns the score of that cell. No score is earned when paint reaches a cell that is already painted.

For each paint drop, find the total score newly earned by Takahashi from that paint drop.

Constraints

  • 1 \leq H \leq 2 \times 10^5
  • 1 \leq W \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • H \times W \leq 4 \times 10^6
  • H \times Q \leq 4 \times 10^6
  • H + Q \leq 2 \times 10^5
  • 0 \leq A_{i,j} \leq 10^9
  • 1 \leq R_t \leq H
  • 1 \leq C_t \leq W
  • 0 \leq D_t \leq H + W
  • All input values are integers

Input

H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
Q
R_1 C_1 D_1
R_2 C_2 D_2
\vdots
R_Q C_Q D_Q
  • The first line contains the number of rows H and the number of columns W of the canvas, separated by a space.
  • In the following H lines, the i-th line contains the scores A_{i,1}, A_{i,2}, \ldots, A_{i,W} separated by spaces.
  • The next line contains the number of paint drops Q.
  • In the following Q lines, the t-th line contains the center row R_t, column C_t, and reach distance D_t of the t-th paint drop, separated by spaces.

Output

Output Q lines.

The t-th line should contain the total score newly earned by Takahashi from the t-th paint drop.

Sample Input 1

3 4
1 2 3 4
5 6 7 8
9 10 11 12
4
2 2 1
1 4 0
3 1 2
2 3 7

Sample Output 1

30
4
21
23

Sample Input 2

2 5
0 5 0 7 1
3 0 4 0 2
5
1 1 0
1 3 1
2 5 3
2 2 0
1 5 0

Sample Output 2

0
16
3
0
0

Sample Input 3

5 7
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8
3 4 2
1 1 3
5 7 1
2 6 4
4 2 0
5 1 5
1 7 0
3 3 10

Sample Output 3

52
30
13
46
6
18
0
0

Sample Input 4

8 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
12
4 5 3
1 10 2
8 1 4
3 7 0
6 6 5
2 2 1
7 9 3
1 1 18
8 10 0
5 3 2
4 10 6
8 5 8

Sample Output 4

875
96
885
0
1121
60
80
123
0
0
0
0

Sample Input 5

1 1
1000000000
4
1 1 0
1 1 1
1 1 2
1 1 0

Sample Output 5

1000000000
0
0
0