← 返回题目列表

AtCoder · awc0065_d

D. 交货范围内的总销售额

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

分数: 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