제출 #1353060

#제출 시각아이디문제언어결과실행 시간메모리
1353060Francisco_MartinBouquet (EGOI24_bouquet)C++20
100 / 100
105 ms18588 KiB
//EGOI 2024 Bouquet
//https://qoj.ac/contest/1764/problem/9183

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

struct Segtree{
    vll tree; ll sz;
    Segtree(ll n){
        sz=1; while(sz<n) sz*=2;
        tree.assign(2*sz,0);
    }
    void update(ll pos,ll delta,ll x,ll lx,ll rx){
        if(rx-lx==1){tree[x]=delta; return;}
        ll m=(lx+rx)/2;
        if(pos<m) update(pos,delta,2*x+1,lx,m);
        else update(pos,delta,2*x+2,m,rx);
        tree[x]=max(tree[2*x+1],tree[2*x+2]);
    }
    void update(ll pos,ll delta){update(pos,delta,0,0,sz);}
    ll query(ll l,ll r,ll x,ll lx,ll rx){
        if(rx<=l || r<=lx) return 0;
        if(l<=lx && rx<=r) return tree[x];
        ll m=(lx+rx)/2;
        return max(query(l,r,2*x+1,lx,m),query(l,r,2*x+2,m,rx));
    }
    ll query(ll l,ll r){return query(l,r,0,0,sz);}
};

int main(){
    ll n;
    cin >> n;
    vll L(n+1), R(n+1); vector<pair<ll,ll>> A[n+2];
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];
    Segtree dp(n+1); dp.update(0,0);
    for(int i=1; i<=n; i++){
        for(auto [a,b]:A[i]) dp.update(a,b);
        ll x=dp.query(0,max(1ll,i-L[i]))+1; A[min(n+1,i+R[i]+1)].push_back({i,x});
    }
    for(auto [a,b]:A[n+1]) dp.update(a,b);
    cout << dp.query(0,n+1) << "\n";
}
#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...