제출 #1328452

#제출 시각아이디문제언어결과실행 시간메모리
1328452settopBouquet (EGOI24_bouquet)C++20
100 / 100
106 ms12436 KiB
#include<bits/stdc++.h>

using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define int long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int MAXN=2e5+10;
typedef pair<int,int> pii;

int n,l[MAXN],r[MAXN],dp[MAXN],seg[4*MAXN];

void add(int ind,int l,int r,int a,int val){
    if(a<l || a>r) return;
    if(l==r){
        seg[ind]=val;
        return;
    }
    int m=(l+r)/2;
    add(2*ind,l,m,a,val); add(2*ind+1,m+1,r,a,val);
    seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}

int query(int ind,int l,int r,int a,int b){
    if(a>r || l>b) return 0;
    if(a<=l && b>=r) return seg[ind];
    int m=(l+r)/2;
    return max(query(2*ind,l,m,a,b),query(2*ind+1,m+1,r,a,b));
}

int32_t main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    fall(i,1,n) cin>>l[i]>>r[i];

    priority_queue<pii,vector<pii>,greater<pii>> fila;

    int ans=0;

    fall(i,1,n){
        while(!fila.empty()){
            auto [d,x]=fila.top();
            if(d<=i){
                add(1,0,n,x,dp[x]);
                fila.pop();
            }
            else break;
        }
        dp[i]=query(1,0,n,0,max(0ll,i-l[i]-1))+1;
        fila.push({i+r[i]+1,i});
        ans=max(ans,dp[i]);
    }
    cout<<ans<<"\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...