# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1148358 | UmairAhmadMirza | Bouquet (EGOI24_bouquet) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=2e5+5;
int const mod=1e9+7;
int L[N],R[N];
int fen[2*N];
int dp[2*N];
void update(int x,int val) {
while(x<N){
fen[x]=max(val,fen[x]);
x+=(x&-x);
}
}
int query(int x){
int res=0;
while(x>0){
res=max(fen[x],res);
x-=(x&-x);
}
return res;
}
int main(){
int n;
cin>>n;
deque<pair<int,int>> ir;
for (int i = 1; i <=n; ++i)
{
cin>>L[i]>>R[i];
ir.push_back({i+R[i],i});
}
sort(ir.begin(), ir.end());
for (int i = 1; i <=n; ++i)
{
dp[i]=1;
if((i-L[i])>1)
dp[i]+=dp[((i-L[i])-1)];
dp[i]=max(dp[i-1],dp[i])
// update(i,dp[i]);
// cout<<dp[i]<<' ';
// while(ir.size() && ir[0].first<=i){
// update(ir[0].second,dp[ir[0].second]);
// ir.pop_front();
// }
}
// cout<<endl;
cout<<dp[n]<<endl;
return 0;
}