Submission #1358604

#TimeUsernameProblemLanguageResultExecution timeMemory
1358604hsuan._.0528Bouquet (EGOI24_bouquet)C++20
24 / 100
90 ms23136 KiB
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+10;

int n;
int r[maxn], l[maxn];
set<int> st;
vector<int> v[maxn];
int dp[maxn];


signed main(){
    ios_base::sync_with_stdio(0);  cin.tie(0);

    cin>>n;
    for(int i=0; i<n; i++)  cin>>l[i]>>r[i];
    for(int i=0; i<n; i++){
        auto it = st.lower_bound( max(0, i-l[i]) );
     //   cout<<i-l[i]<<" \n";
        if( st.empty() or it == st.begin()){
            if(i){
           //     cout<<i<<"  dp= "<<dp[i-1]<<","<<1<<"\n";
                dp[i]=max(1, dp[i-1]);
            }
            else{
            //    cout<<i<<"  dp= "<<1<<"\n";
                dp[i]=1;
            }
        }else{
         //   cout<<i<<"  dp= ("<<*prev(it)<<")"<<dp[ *prev(it) ]+1<<","<<dp[i-1]<<"\n";
            dp[i]=max(dp[ *prev(it) ]+1, dp[i-1]);
        }
        v[ min((int)2e5+5, i+r[i]) ].push_back(i);
        for(int j: v[i])  st.insert(j);
    }
    cout<<dp[n-1];
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...