CUBE-195: Infinite Lime (86%, BS * BS)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 1e18;
const int N = 7e5 + 10;
lli num[N];
lli m;

lli Find(lli x){
    lli l = 1, r = m, mx = 0;
    while(l <= r){
        lli mid = (l + r)/ 2;
        if((lli) num[mid] <= x){
            mx = max(mx, mid);
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return mx;
}

lli Query(lli x){
    lli l = 0, r = INF, mn = INF;
    while(l <= r){
        lli mid = (l + r) / 2;
        lli cal = Find(mid);
        if(mid - cal >= x){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return mn;
}

int main(){

    lli k;
    scanf("%lld%lld", &m, &k);

    for(int i=1;i<=m;i++)
        scanf("%lld", &num[i]);

    sort(num + 1, num + m + 1);

    while(k--){
        lli x;
        scanf("%lld", &x);
        printf("%lld ", Query(x));
    }

    return 0;
}