CUBE-195: Infinite Lime (BS + QS)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
struct Data{ lli st, ed;};
vector < Data > range;
vector < lli > qs;
const int M = 7e5 + 10;
const lli INF = 1e18;
lli del[M];
lli m, Q, n;

lli Query(lli x){
    lli l = 0, r = n - 1, mn = n;
    while(l <= r){
        lli mid = (l + r)/ 2;
        if(qs[mid] < x) l = mid + 1;
        else r = mid - 1, mn = min(mn, mid);
    }
    lli prev = (mn == 0 ? 0: qs[mn-1]);
    return range[mn].st + x - prev - 1;
}

int main(){

    scanf("%lld%lld", &m, &Q);

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

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

    lli prev = 1, sum = 0;
    for(lli i=1;i<=m;i++){
        if(prev == del[i]) prev ++;
        else{
            range.push_back({prev, del[i] - 1});
            sum += del[i] - prev;
            qs.push_back(sum);
            prev = del[i] + 1;
        }
    }
    if(prev <= INF) {
        range.push_back({prev, INF});
        sum += INF - prev + 1;
        qs.push_back(sum);
    }


    n = (lli) range.size();

    for(lli q=1;q<=Q;q++){
        lli x;
        scanf("%lld", &x);
        printf("%lld ", Query(x));
    }

    return 0;
}