分数: 466 分
问题陈述
Takahashi 是一家电信公司的工程师,负责调查道路沿线的无线电状况。
所调查的道路是一条直线,且 N 沿路建有无线电塔。道路用数轴表示,其中 i-th 无线电塔位于坐标 X_i 并有电源输出 B_i.
坐标处的“信号强度” p 定义为所有无线电塔贡献的总和:
f(p) = \sum_{i=1}^{N} \max(0,\ B_i - |p - X_i|)
即每个无线电塔 i 提供的信号强度为 \max(0,\ B_i - |p - X_i|) 协调 p。距离塔越远,信号就越弱,一旦距离至少 10 米,信号就无法到达。 B_i.
高桥的同事青木将进行信号强度调查 Q 间隔。对于每项调查 j,一个区间 给出了 [L_j, R_j] 。找到最大值 f(p) 所有整数坐标 p 在该区间内。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq X_i \leq 2 \times 10^5
- 1 \leq B_i \leq 2 \times 10^5
- 0 \leq L_j \leq R_j \leq 2 \times 10^5
- 所有输入值均为整数。
输入
N Q X_1 B_1 X_2 B_2 : X_N B_N L_1 R_1 L_2 R_2 : L_Q R_Q
- 第一行包含 N,无线电塔的数量,以及 Q,调查数量,以空格分隔。
- 以下 N 行提供有关每个无线电塔的信息。
- 的 (1 + i)第行包含坐标 X_i 和功率输出 B_i 的 i第一个无线电塔,间隔一个空格。
- 以下 Q 行提供有关每个调查的信息。
- 的 (1 + N + j)第行包含左端点 L_j 和右端点 R_j 的间隔 j第次调查,以空格分隔。
输出
输出 Q 行。的 j- 第行应包含以下问题的答案 j第次调查,即最大值 f(p) 所有整数坐标 p 区间内 [L_j, R_j].
示例输入 1
1 2 5 3 0 10 0 3
示例输出 1
3 1
示例输入 2
3 3 2 3 5 4 10 2 0 10 6 10 9 12
示例输出 2
4 3 2
示例输入 3
5 5 0 5 10 3 20 8 15 6 25 4 0 30 12 18 0 5 20 25 0 0
示例输出 3
9 9 5 9 5