Submission #1309558

#TimeUsernameProblemLanguageResultExecution timeMemory
1309558NewtonabcBouquet (EGOI24_bouquet)C++20
100 / 100
162 ms15896 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1<<19;
int l[N],r[N],s[N],dp[N];
vector<pair<int,int>> upd[N];
void update(int l,int r,int idx,int a,int b){
    if(a<l || a>r) return;
    if(l==r){
        s[idx]=b;
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2,a,b);
    update(m+1,r,idx*2+1,a,b);
    s[idx]=max(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a,int b){
    if(b<l || a>r) return INT_MIN;
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i] >>r[i],l[i]=min(l[i],i-1),r[i]=min(r[i],n-i);
    for(int i=1;i<=n;i++){
        for(auto [ind,val]:upd[i]){
            update(0,n+1,1,ind,val);
        }
        dp[i]=query(0,n+1,1,0,i-l[i]-1)+1;
        upd[i+r[i]+1].push_back({i,dp[i]});
    }
    cout<<*max_element(dp+1,dp+n+1);
}
#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...