分数: 6 点
警告
2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
在二维平面上,有 N 边长与 x 轴或 y 轴平行的方形土地。的 i第一个图可以表示为区域 xmin_i \leq x \leq xmin_i + D_i, ymin_i \leq y \leq ymin_i + D_i。每个地块都有固定成本,并且该地块的成本 i第一个图是 C_i.
在这里, Q 施工计划已考虑。的 j第一个计划旨在在坐标处建造一座建筑物 (A_j, B_j).
每个计划的成本是覆盖(或接触)施工点的所有地块的成本之和。
查找每个计划的成本。
约束
- 1 \leq N \leq 50000
- 1 \leq Q \leq 100000
- -10^9 \leq xmin_i, ymin_i \leq 10^9
- 1 \leq D_i \leq 10^9
- 0 \leq C_i \leq 10^9
- -10^9 \leq A_i, B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q xmin_1 ymin_1 D_1 C_1 xmin_2 ymin_2 D_2 C_2 : xmin_N ymin_N D_N C_N A_1 B_1 : A_Q B_Q
输出
打印 Q 行。的 j- 第行应包含 j第一个计划。
示例输入 1
2 4 1 3 6 10 3 6 6 20 4 7 -1 -1 1 4 7 13
示例输出 1
30 0 10 0
- 对于 1-st plan,两个地块都覆盖了施工点,所以我们应该打印 10 + 20 = 30.
- 对于 2-nd计划,两个图都没有覆盖施工点,所以我们应该打印 0.
- 对于 3-rd计划, 1-st 图覆盖了构造点,所以我们应该打印 10.
- 对于 4-th plan,两个图都没有覆盖施工点,所以我们应该打印 0.
示例输入 2
2 3 -3 5 4 100 1 9 7 30 1 9 1 8 8 10
示例输出 2
130 100 30
- 对于 1-st plan,两个地块都覆盖了施工点,所以我们应该打印 100 + 30 = 130.
- 对于 2-nd 计划, 1-st 图覆盖了构造点,所以我们应该打印 100.
- 对于 3-rd计划, 2-nd 图覆盖了构造点,所以我们应该打印 30.
示例输入 3
10 10 17 2 17 1000000000 7 12 12 1000000000 2 12 8 1000000000 2 12 2 1000000000 3 9 16 1000000000 8 13 15 1000000000 8 1 3 1000000000 15 9 17 1000000000 16 5 5 1000000000 13 12 9 1000000000 17 3 4 10 1 9 5 3 17 12 14 19 19 17 17 11 16 17 12 16
示例输出 3
1000000000 1000000000 0 0 5000000000 4000000000 6000000000 3000000000 5000000000 3000000000