Submission #72400773

---

Source Code Expand

/*
C++に変換

方針: 二分探索
1: Aをソートする
2: 各クエリに答える
  2-1: 区間[X,e]に含まれるAの要素数kとしたとき、count = (e-X+1)-k がYになる最小のeを求める
    *e-X+1: 区間[X,e]には数字がX,X+1,X+2,...,eのe-X+1個 存在する という意味
    *countは単調増加: なぜなら区間が1増えるごとにkは0または1のみ増えるので(countが減少することはない)
  2-2: 2-1の結果に応じて答えを求める
  
例:
A = [1,2,3,9,16]
  ・6以上15以下の場合:  (15-6+1) -1 = 9個  // k=1(9)
  ・6以上16以下の場合:  (16-6+1) -2 = 9個  // k=2(9,16)
  ・6以上17以下の場合:  (17-6+1) -2 = 10個 // k=2(9,16)
  -> Y=10なのでe=17が答え
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 区間 [l, r] において data に含まれない整数が k 個以上あるか
bool check_range(const vector<ll>& data, ll l, ll r, ll k) {
    // Python の bisect_left / bisect_right に対応
    auto it_l = lower_bound(data.begin(), data.end(), l);
    auto it_r = upper_bound(data.begin(), data.end(), r);

    ll count_in_range = it_r - it_l;           // 区間 [l, r] に含まれる data の個数
    ll count = (r - l + 1) - count_in_range;   // 含まれない整数の個数

    return count >= k;
}

// 二分探索で条件を満たす最小の e を求める
ll calc_right_val(const vector<ll>& A, ll X, ll Y) {
    ll l = X - 1;
    ll r = 3LL * 1000000000 + 1; // 3 * 10^9 + 1

    while (r - l > 1) {
        ll mid = (l + r) / 2;
        if (check_range(A, X, mid, Y)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    // l or r が答え
    if (check_range(A, X, l, Y)) {
        return l;
    } else {
        return r;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    while (Q--) {
        ll X, Y;
        cin >> X >> Y;
        cout << calc_right_val(A, X, Y) << '\n';
    }

    return 0;
}

Submission Info

Judge Result