Submission #1165824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165824		em4ma2	Bouquet (EGOI24_bouquet)	C++20	100 / 100	104 ms	28588 KiB

Main

//                          بسم الله الرحمن الرحيم
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define int long long
#define pb push_back
#define endl '\n'
#define ld long double
#define applejuice ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

const ll mod=1e9+7;
const ll inf=1e18;
const ll mxsz=100+4;
const ld pi=acos(-1.0);

map<int,int>mp;

signed main() {
    applejuice;

    int n;
    cin>>n;
    int l[n],r[n];
    bool flag=false;
    for (int i=0;i<n;i++){
        cin>>l[i]>>r[i];
    }
    int dp[n+1]={};
    vector<vector<int>>cur(n+1);
    mp[-inf]=0;
    //cout<<"eifohe";
    for (int i=0;i<n;i++){
        for (auto j:cur[i]){
            auto x=mp.lower_bound(j);
            //int mm = *(--x->second)
            if(prev(x)->second>dp[j]) continue;
            while(x!=mp.end() && x->second<=dp[j]){
                mp.erase(x++);
            }
            //cout<<mp[j]<<" ";
            mp[j]=dp[j];
            //cout<<mp[j]<<" ";
        }
        //cout<<dp[i]<<" ";
        dp[i]=(--mp.lower_bound(i-l[i]))->second+1;
        //cout<<dp[i]<<" ";
        //cout<<"oufr";
        cur[min(n,i+r[i]+1)].pb(i);
    }
    /*for (int i=0;i<n;i++){
        cout<<dp[i]<<" ";
    }*/
    /*for (auto [x,y]:mp){
        cout<<x<<" "<<y<<endl;
    }*/
    int ans=0;
    for (auto x:dp){
        ans=max(x,ans);
    }
    cout<<ans;
    /*int dpl[n],dpr[n];
    dpl[0]=1,dpr[n-1]=1;
    if (n<=1000){
        int dp[n];
        dp[0]=1;
        for (int i=0;i<n;i++){
            if(i>0)dp[i]=1;
            for (int j=0;j<i;j++){
                if(j<i && max(a[i].first,a[j].second)<i-j){
                    dp[i]=max(dp[i],dp[j]+1);
                    //cout<<i<<" "<<j<<" "<<dp[i]<<" "<<dp[j]<<" ";
                }
            }
        }
        int mx=0;
        for (auto x:dp)mx=max(x,mx);
        //for (auto x:dp)cout<<x<<" ";
        cout<<mx;
        return 0;
    }
    if (flag)
        cout<<(n-1)/(a[0].first+1)+1;
    else {
        for (int i = 0; i < n; i++) {
            if (i > 0)dpl[i] = dpl[i - 1];
            //cout<<i<<" "<<a[i].second;
            if (i > a[i].first) {
                dpl[i] = max(dpl[i], dpl[i - a[i].first - 1] + 1);
            }
        }
        cout<<dpl[n-1]<<endl;
    }*/
    //cout<<dpr[0];
    /*for (int i=n-1;i>=0;i--){
        if(i<n-1)dpr[i]=dpr[i+1];
        //cout<<dpr[n-1]<<endl;
        if(i>a[i].second){
            //cout<<"ihef";
            dpr[i]=max(dpr[i],dpr[i+a[i].first+1]+1);
        }
    }*/
    /*for (auto x:dpl){
        cout<<x<<" ";
    }cout<<endl;
    for (auto x:dpr){
        cout<<x<<" ";
    }*/
    //int mx=0;
    //cout<<dpl[n-1]-dpr[n-1]+1;

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30