← 返回题目列表

AtCoder · abc364_d

G. 第 K 个最近的

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

分数: 425 点

问题陈述

有 N+Q 点 A_1,\dots,A_N,B_1,\dots,B_Q 在数轴上,其中点 A_i 有一个坐标 a_i 和点 B_j 有一个坐标 b_j.

对于每个 j=1,2,\dots,Q,回答以下问题:

  • 让 X 是其中的一点 A_1,A_2,\dots,A_N 那就是 k_j- 第一个最接近的点 B_j。求点之间的距离 X 和 B_j。 更正式地说,让 d_i 是点之间的距离 A_i 和 B_j。排序 (d_1,d_2,\dots,d_N) 按升序排列得到序列 (d_1',d_2',\dots,d_N')。查找 d_{k_j}'.

约束

  • 1 \leq N, Q \leq 10^5
  • -10^8 \leq a_i, b_j \leq 10^8
  • 1 \leq k_j \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

输出

打印 Q 行。 的 l第行 (1 \leq l \leq Q) 应包含问题的答案 j=l 作为整数。


示例输入 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

示例输出 1

7
3
13

让我们解释一下第一个查询。

到点的距离 A_1, A_2, A_3, A_4 点 B_1 是 1, 1, 7, 8,分别是第三个最接近点 B_1 是点 A_3。 因此,打印点之间的距离 A_3 和点 B_1,即 7.


示例输入 2

2 2
0 0
0 1
0 2

示例输出 2

0
0

可能有多个点具有相同的坐标。


示例输入 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

示例输出 3

11
66
59
54
88