本問題のように「\(k\) 番目に○○な△△を求める」という問題では、しばしば二分探索が解法の初手として用いられます。実際、本問題においても二分探索を用いることができます。具体的には、\(f_j(x)=(\)点 \(A_1,A_2,\dots,A_N\) のうち点 \(B_j\) との距離が \(x\) 以下であるようなものの数\()\) と定めると、「点 \(A_1,A_2,\dots,A_N\) のうち点 \(B_j\) との距離が \(k_j\) 番目に近い点を求める」という問題は「\(f_j(x)\geq k_j\) を満たす最小の \(x\) を求める」という問題に帰着されます。\(f_j(x)\) には明らかに単調性があることから、二分探索を用いれば、「ある \(j,x\) に対して \(f_j(x)\) を求める」というクエリを \(O(Q\log A)\) 回（ここで \(A\) は座標としてありうる数の範囲）処理することで本問題を解くことができます。

「ある \(j,x\) に対して \(f_j(x)\) を求める」すなわち「\(b_j-x\) 以上 \(b_j+x\) 以下の範囲内にある \(a\) の要素数を求める」という問題は、最初に \(a\) をソートしておけば、これもまた二分探索によって高速に処理することができます。

全体の計算量は \(O(N\log N + Q\log A\log N)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    while (q--) {
        int b, k;
        cin >> b >> k;
        auto f = [&](int x) -> bool {
            // (# of points in [b-x, b+x]) >= k
            auto lb = lower_bound(a.begin(), a.end(), b - x);
            auto ub = upper_bound(a.begin(), a.end(), b + x);
            return ub - lb >= k;
        };
        int ng = -1, ok = (int) 2e8 + 10;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (f(mid)) ok = mid;
            else ng = mid;
        }
        cout << ok << '\n';
    }
}