PROG-1142: ศูนย์ประชุม (convention)

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5;
const int INF = 1e9;
using pi = pair <int, int>;
pi ar[N+10];
int tree[1<<20], lazy[1<<20];
vector <int> pst;
int sz;
int BS(int x);

void Lazy(int idx, int l, int r){
    if(lazy[idx] == 0) return;
    if(l != r){
        lazy[2*idx] += lazy[idx];
        lazy[2*idx+1] += lazy[idx];
    }
    tree[idx] += lazy[idx];
    lazy[idx] = 0;
}

void update(int idx, int l, int r, int s, int e){
    Lazy(idx, l, r);
    if(l > e or r < s) return;
    if(s <= l and r <= e){
        if(l != r){
            lazy[2*idx] ++;
            lazy[2*idx + 1] ++;
        }
        tree[idx] ++;
        return;
    }
    int mid = (l + r) / 2;
    update(2*idx, l, mid, s, e);
    update(2*idx + 1, mid + 1, r, s, e);
    tree[idx] = max(tree[2*idx], tree[2*idx+1]);
}

int query(int idx, int l, int r, int s, int e){
    Lazy(idx, l, r);
    if(l > e or r < s) return -INF;
    if(s <= l and r <= e) return tree[idx];
    int mid = (l + r) / 2;
    int L = query(2*idx, l, mid, s, e);
    int R = query(2*idx+1, mid+1, r, s, e);
    return max(L, R);
}

int main(){

    int n, k;
    scanf("%d%d", &n, &k);

    for(int i=1;i<=n;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        ar[i] = {u, v};
        pst.push_back(u);
        pst.push_back(v);
    }

    sort(pst.begin(), pst.end());
    pst.resize( unique(pst.begin(), pst.end()) - pst.begin() );
    pst.insert(pst.begin(), 0);
    sz = pst.size();

    for(int i=1;i<=n;i++){
        int s = BS(ar[i].first);
        int e = BS(ar[i].second);
        int q = query(1, 1, sz-1, s, e);
        if(q < k) {
            printf("yes");
            update(1, 1, sz-1, s, e);
        }
        else printf("no");
        printf("\n");
    }

    return 0;
}

int BS(int x){
    int l = 1, r = sz-1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(pst[mid] == x) return mid;
        else if(pst[mid] < x) l = mid+1;
        else r = mid-1;
    }
}