Submission #72382595

---

Source Code Expand

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

bool check(const vector<int>& v, int mid, int s, int Y)
{
    // count of A in [s, mid]
    int cnt = upper_bound(v.begin(), v.end(), mid)
            - lower_bound(v.begin(), v.end(), s);

    // total numbers in [s, mid]
    int total = mid - s + 1;

    int missing = total - cnt;
    return missing >= Y;
}

void solve()
{
    int n,q; 
    cin>>n>>q;

    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(), v.end());

    while(q--)
    {
        int s,Y;
        cin>>s>>Y;

        int l = s;
        int r = s + Y + n;   // safe upper bound

        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(v, mid, s, Y))
                r = mid;
            else
                l = mid + 1;
        }

        cout << l << "\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}

Submission Info

Judge Result