제출 #1357276

#제출 시각아이디문제언어결과실행 시간메모리
1357276mxhrvsBouquet (EGOI24_bouquet)C++20
100 / 100
102 ms18608 KiB
#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";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…