← 返回题目列表

AtCoder · awc0080_e

E. 油漆滴

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥正在网格画布上玩绘画游戏 H 行和 W 列。牢房位于 i从顶部算起的第行和 j从左边算起的第列称为单元格 (i, j).

细胞 (i, j) 有一个分数 A_{i,j} 分配给它。最初,没有绘制任何单元格。

高桥将把颜料滴到画布上 Q 次。

在 t-th 油漆滴,画布上与单元格曼哈顿距离的所有单元格 (R_t, C_t) 最多是 D_t 已涂漆。

换句话说,在所有单元格中 (i, j) 满意 1 \leq i \leq H 和 1 \leq j \leq W,所有单元格满足

|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
  • 第一行包含行数 H 和列数 画布的 W ,以空格分隔。
  • 在下面 H 行, i- 第行包含分数 A_{i,1}, A_{i,2}, \ldots, A_{i,W} 以空格分隔。
  • 下一行包含油漆滴数 Q.
  • 在下面 Q 行, t第行包含中心行 R_t,列 C_t,并到达距离 D_t 的 t第一个油漆滴,以空格分隔。

输出

输出 Q 行。

的 t- 第行应包含高桥新获得的总分 t-th 油漆滴。


样本输入 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