Submission #1276700

#TimeUsernameProblemLanguageResultExecution timeMemory
1276700coderg300711Bouquet (EGOI24_bouquet)C++20
100 / 100
149 ms27044 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
vector<ll> tree;

void update(ll v,ll p,ll tl=0,ll tr=n-1,ll i=1){
   if(tl==tr){
    tree[i]=v;
    return;
   }
   ll tm=(tl+tr)>>1;
   if(p<=tm)update(v,p,tl,tm,i<<1);
   else update(v,p,tm+1,tr,(i<<1)+1);
   tree[i]=max(tree[(i<<1)],tree[(i<<1)+1]);
}

ll query(ll l,ll r,ll tl=0,ll tr=n-1,ll i=1){
    if(l>r)return 0;
    if(tl==l && tr==r)return tree[i];
    ll tm=(tl+tr)>>1;
    ll x1=query(l,min(r,tm),tl,tm,i<<1),x2=query(max(l,tm+1),r,tm+1,tr,(i<<1)+1);
    return max(x1,x2);
}

signed main(){
    cin>>n;
    tree.resize(4*n);
    vector<ll> l(n),r(n),dp(n);
    vector<vector<ll>> all(2*n);
    for(ll i=0;i<n;i++)cin>>l[i]>>r[i];
    for(ll i=0;i<n;i++){
        for(auto x:all[i])update(dp[x],x);
        dp[i]=query(0,i-l[i]-1)+1;
        all[i+r[i]+1].push_back(i);
    }
    sort(dp.begin(),dp.end());
    cout<<dp.back()<<'\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...