Submission #1266543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266543		coderg	Bouquet (EGOI24_bouquet)	C++20	100 / 100	139 ms	27036 KiB

Main

/** 02.09.2025 */
#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);
    }
    ll ans=*max_element(dp.begin(),dp.end());
    cout<<ans<<'\n';
}

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