Submission #1344509

#TimeUsernameProblemLanguageResultExecution timeMemory
1344509goulthenBouquet (EGOI24_bouquet)C++20
100 / 100
188 ms20196 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define endl '\n'

const int MAXN = 2e5+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
int l[MAXN], r[MAXN], seg[4*MAXN];

int query(int i, int l, int r, int li, int ri) {
    if(r < l || r < li || l > ri) return 0;
    if(l>=li && r <= ri) return seg[i];

    int mid = (l+r)>>1;
    return max(query(2*i,l,mid,li,ri), query(2*i+1,mid+1,r,li,ri));
}

void update(int i, int l, int r, int ti, int x) {
    if (r < l || ti < l || ti > r) return;
    if(l==r) {
        seg[i] = max(seg[i],x);
        return;
    }
    int mid = (l+r)>>1;
    update(2*i, l,mid,ti,x);
    update(2*i+1,mid+1,r,ti,x);
    seg[i] = max(seg[2*i],seg[2*i+1]);
}

void solve() {
    int n; cin >> n;
    rep(i,1,n) cin >> l[i] >> r[i];
    set<array<int,3>> st;
    rep(i,1,n+1) {
        while(!st.empty()) {
            auto [id,j,v] = *st.begin();
            if(id>i) break;
            st.erase(st.begin());
            update(1,1,n,j,v);
        }
        if(i>n) break;
        int x = query(1,1,n,1,i-l[i]-1) + 1;
        st.insert({min(n+1,i+r[i]+1),i,x});
    }

    cout << query(1,1,n,1,n);
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;

    while (tt--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...