実行時間制限: 3 sec / メモリ制限: 1024 MB / Difficulty: 1136

問題概要

数直線上に $N + Q$ 個の点 $A_1, A_2, \cdots, A_N, B_1, B_2, \cdots. B_Q$ があり、座標は $A_i(a_i), B_j(b_j) : (1 \leq i \leq N, 1 \leq j \leq Q)$ である。各 $j$ について、以下の問いの答えを出力せよ。 - 問. 点 $A_1, A_2, \cdots, A_N$ のうち点 $B_j$ との距離が $k_j$ 番目に近い点を $X$ としたとき、点 $X$ と点 $B_j$ との距離を求めよ。

制約

入力はすべて整数。
$1 \leq N, Q \leq 10^5$
$-10^8 \leq a_i, b_j \leq 10^8$
$1 \leq k_j \leq N$

考察

以前、 ABC365-C の記事で「ある条件を満たす $x$ の最大化・最小化」には二分探索が有効と書いたが、実は「ソートされた数列の中で $k$ 番目に条件を満たすものを求める」場合にも二分探索を使うことができる (なぜなら、ある値 $x$ を決め打ったときに、「数列の $k$ 番目の要素は $x$ 以下である」ことと「数列内に $x$ 以下の値が $k$ 個以上含まれる」ことは同値だから)。

本問では、 $|A_i - B_j| \leq x \: (1 \leq i \leq N)$ となる $i$ の個数を $c_j(x)$ とすれば、「 $c_j(x) \leq k$ を満たす $x$ の最小化」をすればよいことになる。サンプルケース1で考えてみると、下図のようになる。

めぐる式二分探索の動きをトレースした (`ok`の初期値は、本来は $10^9$ などにすべき) 。

めぐる式二分探索の動きをトレースした (`ok`の初期値は、本来は $10^9$ などにすべき) 。

距離は負になることはないので、ngの初期値は $-1$ とした。

これより、各 $j$ に関する問題は対数時間で処理することができる。

あとは $c_j(x)$ をどのように求めるかだが、 $N$ は最大で [tex: 10⁵] になるので、単純にループを回していたのでは間に合わない。そこで、ここでも二分探索を使おう。ソートした数列 $A$ に対して、閉区間 $[a, b$ ] に含まれる要素の個数は、upper_bound(A.begin(), A.end(), b) - lower_bound(A.begin(), A.end(), a)のように書くと求めることができる。

qiita.com

したがって、これも対数時間で求めることができ、実行時間に間に合う。

コード

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr auto INF = 1e+9;

// ======================================== //

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    sort(all(A));

    rep(q, 0, Q)
    {
        int b, k;
        cin >> b >> k;

        int ok = INF, ng = -1;
        while (abs(ok - ng) > 1)
        {
            int mid = (ok + ng) / 2;
            int right = upper_bound(all(A), b + mid) - A.begin();
            int left = lower_bound(all(A), b - mid) - A.begin();
            if (right - left >= k)
                ok = mid;
            else
                ng = mid;
        }

        cout << ok << endl;
    }
}