BOJ 14587 도미노 (Large)

void solve(){
    int N; cin >> N;
    vector<ll> X(N), H(N);
    
    vector<pll> dominos(N);
    rep(i, 0, N) cin >> dominos[i].first >> dominos[i].second;
    sort(all(dominos));
    rep(i, 0, N){
        X[i] = dominos[i].first;
        H[i] = dominos[i].second;
    }

    SegmentTreeMinMax ST_min(N), ST_max(N);
    
    // calc leftmost
    ST_min.set(0, 0);
    rep(i, 1, N){
        ll val = X[i] - H[i];
        auto idx = lower_bound(all(X), val) - X.begin();
        auto Q = ST_min.query(idx, i-1);
        ST_min.set(i, min((ll)i, ST_min.query(idx, i-1).first));
    }
    
    // calc rightmost
    ST_max.set(N-1, N-1);
    rrep(i, 0, N-1){
        ll val = X[i] + H[i];
        auto idx = upper_bound(all(X), val) - X.begin() - 1;
        auto Q = ST_min.query(i+1, idx);
        ST_max.set(i, max((ll)i, ST_max.query(i+1, idx).second));
    }

    vector<int> DP(N, 1e9);
    DP[0] = 1;
    DP[ST_max.get_val(0)] = 1;
    rep(i, 1, N){
        int lft = ST_min.get_val(i)-1;
        if(lft < 0) DP[i] = 1;
        else DP[i] = min(DP[i], DP[lft] + 1);

        int rht = ST_max.get_val(i);
        DP[rht] = min(DP[rht], DP[i-1] + 1);
    }
    cout << DP[N-1];
}