← 返回题目列表

AtCoder · past202004_n

N. 建筑施工

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

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