/** 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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |