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