Submission #1178440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178440		Choco	Bouquet (EGOI24_bouquet)	C++20	100 / 100	52 ms	14456 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define Study ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first 
#define ss second
#define ins insert
#define all(x) x.begin(),x.end()
#define fori(x,y,z) for(ll x=y;x<=z;x++)
const ll INF=1e9;
const ll sz=2e5+10;
const ll mod=1e9+7;
ll fw[sz];
void update(ll ind,ll val){
  while(ind<sz){
    fw[ind]=max(fw[ind],val);
    ind+=(ind&(-ind));
  }
}
ll query(ll ind){
  ll res=0;
  while(ind>0){
    res=max(fw[ind],res);
    ind-=(ind&(-ind));
  }
  return res;
}
void work(){
  ll n;
  cin>>n;
  vector<ll>dp(sz);
  vector<vector<ll>>upd(sz);
  ll ans=0;
  fori(i,1,n){
    ll l,r;
    cin>>l>>r;
    if(i-1<=l)
    dp[i]=1;
    else
    dp[i]=query(i-l-1)+1;
    ans=max(ans,dp[i]);
    upd[min(i+r,n)].pb(i);
    for(auto x: upd[i])
    update(x,dp[x]);
  }
  cout<<ans;
}
int main(){
  Study;
  ll t=1;
  //cin>>t;
  fori(i,1,t){
    work();
  }
}

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