# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1148451 | SyedSohaib_123 | Bouquet (EGOI24_bouquet) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define append push_back
#define int long long
const int N=4e5+10,LG=21;
int mod=998244353;
vector<pair<int,int>>g[N];
int dp[N],val[N],par[N];
int get(int a){
if(a==par[a]) return a;
return get(par[a]);
}
void solve(int tst){
int n;
cin>>n;
int ans=0;
set<int>s;
par[0]=0;
for(int i=1;i<=n;i++) dp[i]=1,par[i]=i-1;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
for(auto [ind,v]:g[i]){
for(int j=ind;j>=1;j--){
if(par[j]==j){
val[ind]=max(val[ind],val[j]);
break;
}
}
par[ind]=ind;
}
int x=max(0ll,i-l-1),y=i+1+r;
for(int j=ind;j>=1;j--){
if(par[j]==j){
dp[ind]=max(dp[ind],val[j]);
break;
}
}
if(y<n) g[y].append({i,dp[i]});
ans=max(ans,dp[i]);
val[i]=dp[i];
}
cout<<ans<<endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
for(int i=1;i<=t;i++)
solve(i);
}