#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) (x).begin(), (x).end()
int n;
vector<int> seg;
int qry(int l, int r){
l += n, r += n;
int ans = 0;
while(l < r){
if(l&1) ans = max(ans, seg[l++]);
if(r&1) ans = max(ans, seg[--r]);
l /= 2, r /= 2;
}
return ans;
}
void upd(int i, int x){
seg[i += n] = x;
for(i/=2; i; i/=2) seg[i] = max(seg[2*i], seg[2*i+1]);
}
void solve(){
cin >> n;
seg.resize(2*n);
vector<int> l(n), r(n);
for(int i = 0; i < n; i++) cin >> l[i] >> r[i];
vector<int> dp(n);
vector<vector<int>> events(2*n);
for(int i = 0; i < n; i++){
dp[i] = qry(0, i-l[i]) + 1;
events[i+r[i]].push_back(i);
for(int j : events[i]) upd(j, dp[j]);
}
cout << *max_element(all(dp)) << "\n";
}
int main(){
cin.tie(0)->sync_with_stdio(false);
solve();
}
# | 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... |