Submission #1240881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240881		aren_dance	Bouquet (EGOI24_bouquet)	C++20	100 / 100	107 ms	21576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=5e5;
int n;
int l[N];
int r[N];
int dp[N];
int fw[N];
vector<int> g[N];
void update(int pos,int new_val){
    for(;pos<N;pos+=(pos&-pos)){
        fw[pos]=max(fw[pos],new_val);
    }
}
int get(int pos){
    int answ=0ll;
    for(;pos>0;pos-=(pos&-pos)){
        answ=max(answ,fw[pos]);
    }
    return answ;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>l[i]>>r[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;++i){
        for(auto j:g[i]){
            update(j,dp[j]);
        }
        int x=0;
        dp[i]=1;
        dp[i]=max(1,get(i-l[i]-1)+1);
        g[i+r[i]+1].push_back(i);
    }
    int mx=0;
    for(int i=1;i<=n;++i){
        mx=max(mx,dp[i]);
    }
    cout<<mx<<'\n';
    return 0;
}

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