#include<bits/stdc++.h>
#define meta int tm = tl + (tr - tl) / 2, x = (i << 1) + 1, y = x + 1
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;
int st[maxn * 4] {};
void update(int i, int tl, int tr, int pos, int val) {
if(tl == tr) {
st[i] = val;
return;
}
meta;
if(pos <= tm) update(x, tl, tm, pos, val);
else update(y, tm + 1, tr, pos, val);
st[i] = max(st[x], st[y]);
}
int query(int i, int tl, int tr, int l, int r) {
if(l <= tl && tr <= r) return st[i];
if(l > tr || tl > r) return 0;
meta;
if(r <= tm) return query(x, tl, tm, l, r);
else if(l > tm) return query(y, tm + 1, tr, l, r);
else return max(query(x, tl, tm, l, tm), query(y, tm + 1, tr, tm + 1, r));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> l(n + 1), r(n + 1);
vector<int> v[n * 2 + 1], dp(n + 1, 0);
for(int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
v[i + r[i] + 1].push_back(i);
}
for(int i = 1; i <= n; i++) {
for(int x : v[i]) {
update(0, 0, n, x, dp[x]);
}
int r = max(0, i - l[i] - 1);
int X = query(0, 0, n, 0, r);
dp[i] = X + 1;
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
# | 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... |