시도 횟수: 3회

해결한 시간: 72:20

핵심 아이디어

<aside> 💡

$X$보다 크거나 같은 $Y$번째 수를 $ans$라고 하자.

임의의 $k$를 잡았을 때 $k-X+1 - [X,k]\text{구간의} a_i\text{개수} = Y$라면 $k$는 $ans$의 후보다.

값이 $Y$보다 크다면 더 작은 $k$중 $ans$의 후보가 있다.

이분탐색으로 $k$의 최솟값을 구하면 된다. $O(q\log (N\log N))$로 해결할 수 있다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, q;
map<int, int> sv;

int main()
{
    FASTIO;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i<n; i++) cin >> a[i];

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    for(int cq = 0; cq<q; cq++){
        int x, y;
        cin >> x >> y;

        ll lo = x-2+y;
        ll hi = 2e+9+5;
        while(lo+1<hi){
            ll mid = lo+hi>>1;
            int cnt = upper_bound(a.begin(), a.end(), mid)-lower_bound(a.begin(), a.end(), x);
            
            if(mid-x+1-cnt >= y) hi = mid;
            else lo = mid;
        }
        cout << hi << "\\n";
    }
    
    return 0;
}

복기