PROG-1138: หนังสือเวทมนตร์ (magicbook)

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 1e5;
using pi = pair <int, int>;
int tree[1 << 19];
pi ar[N+10];
vector <int> pst;
int sz;

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

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

int find_x(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;
    }
}

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

int update(int idx, int l, int r, int x, int a){
    if(l == r) return tree[idx] = max(tree[idx], a); // dp
    int mid = (l + r) / 2;
    if(x <= mid) return tree[idx] = max( update(2*idx, l, mid, x, a), tree[2*idx+1]);
    else return tree[idx] = max(tree[2*idx], update(2*idx+1, mid+1, r, x, a));
}

int main(){

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

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

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

    int ans = 0;
    for(int i=1;i<=n;i++){
        int x = ar[i].first;
        int a = ar[i].second;
        int l = find_min(x - k);
        int r = find_max(x + k);
        int mx = query(1, 1, sz-1, l, r);
        if((mx == 0 and abs(x-s) <= k) or mx != 0) mx += a;
        update(1, 1, sz-1, find_x(x), mx);
        ans = max(ans, mx);
    }

    printf("%d", ans);

    return 0;
}