#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ertunt return
#define vodka void
using namespace std;
struct segtree{
ll n;
vector<ll>d;
segtree(ll n): n(n){
d.resize(4*n);
build(1,1,n);
}
vodka build(ll v, ll l, ll r){
if(l == r){
d[v] = 0;
ertunt;
}
ll m = (l+r)/2;
build(v*2,l,m);
build(v*2+1,m+1,r);
d[v] = max(d[v*2],d[v*2+1]);
}
vodka update(ll v,ll l, ll r, ll pos, ll val){
if(pos < l or pos > r)ertunt;
if(l == r){
d[v] = max(d[v],val);
ertunt;
}
ll m = (l+r)/2;
update(v*2,l,m,pos,val);
update(v*2+1,m+1,r,pos,val);
d[v] = max(d[v*2],d[v*2+1]);
}
ll query(ll v, ll l, ll r, ll L, ll R){
if(R < l || r < L) ertunt 0ll;
if(L<=l&&r<=R) ertunt d[v];
ll m = (l+r)/2;
ertunt max(query(v*2,l,m,L,R),query(v*2+1,m+1,r,L,R));
}
};
int main() {
ll n;
cin >> n;
ll l[n+1],r[n+1];
vector<ll>dis[n+2];
for(ll i = 1; i <= n; i++){
cin >> l[i] >> r[i];
dis[min(i+r[i]+1,n+1)].pb(i);
}
segtree gang(n+1);
vector<ll>dp(n+1,1);
for(ll i = 1; i <= n; i++){
for(auto x : dis[i]){
gang.update(1,1,n+1,x,dp[x]);
}
dp[i] = gang.query(1,1,n+1,1,max(0ll,i-l[i]-1))+1;
}
cout << *max_element(all(dp));
}
# | 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... |