分数: 400 分
问题陈述
一个城镇有 N 商店。城镇被表示为一个具有整数坐标的平面,其中 i第商店位于坐标 (X_i, Y_i) 的销售额为 C_i 日元。请注意,同一坐标可能存在多个商店。
青木正在考虑 M 配送中心的候选位置。对于 j-th 候选者,集线器放置在坐标处 (P_j, Q_j),配送范围覆盖曼哈顿范围内的所有地点 K_j.
具体来说,商店 i is 可交付成果 从中心 j-第一个候选者当且仅当:
| X_i - P_j | + | Y_i - Q_j | \le K_j
对于每个候选者,查找所有可交付商店的总销售额。如果没有商店可交付,则输出 0.
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- N + M \leq 1.5 \times 10^5
- 0 \leq X_i \leq 1000
- 0 \leq Y_i \leq 1000
- 1 \leq C_i \leq 10^4
- 0 \leq P_j \leq 1000
- 0 \leq Q_j \leq 1000
- 0 \leq K_j \leq 2000
- 所有输入值均为整数
输入
N M X_1 Y_1 C_1 X_2 Y_2 C_2 \vdots X_N Y_N C_N P_1 Q_1 K_1 P_2 Q_2 K_2 \vdots P_M Q_M K_M
- 第一行包含商店数量 N 以及中心候选人的数量 M,用空格分隔。
- 以下 N 行给出每个商店的信息。
- 的 (1 + i)第行包含坐标 (X_i, Y_i) 的 i第店铺及其销售额 C_i,用空格分隔。
- 以下 M 行给出了每个候选人的信息。
- 的 (1 + N + j)第行包含中心坐标 (P_j, Q_j) 和最大输送距离 K_j 为 j- 第一个候选者,以空格分隔。
输出
关于 j第行 (1 \leq j \leq M),输出该店铺可交付的总销售额 j- 第一个候选人。
示例输入 1
4 3 0 0 10 1 0 20 2 2 30 1 1 40 0 0 0 1 0 1 2 1 2
示例输出 1
10 70 90
示例输入 2
5 4 2 3 15 2 3 25 5 5 40 0 1 10 3 1 30 2 3 0 4 4 1 3 2 2 0 0 10
示例输出 2
40 0 70 120
示例输入 3
12 7 0 0 11 2 4 7 4 1 13 5 5 20 6 2 9 7 7 14 8 3 6 1 8 10 3 6 12 9 0 15 4 4 18 6 6 16 0 0 0 4 4 2 6 3 3 8 8 10 2 7 1 5 1 4 9 9 0
示例输出 3
11 45 69 127 0 60 0
示例输入 4
22 10 0 0 5 100 200 7 150 150 9 200 100 11 250 300 13 300 250 15 400 400 17 500 500 19 600 450 21 700 700 23 800 200 25 900 900 27 1000 1000 29 1000 0 31 0 1000 33 450 550 35 550 450 37 350 650 39 650 350 41 200 800 43 800 800 45 500 0 47 0 0 0 1000 1000 0 500 500 100 500 500 1000 250 250 150 750 250 100 0 1000 200 1000 0 500 300 700 200 400 100 250
示例输出 4
5 29 91 572 28 25 33 103 82 73
示例输入 5
1 4 1000 1000 9999 1000 1000 0 999 1000 0 0 0 1999 0 0 2000
示例输出 5
9999 0 0 9999