← 返回题目列表

AtCoder · awc0062_e

E. 无线电塔和信号强度

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

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