#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())
const int MXN = 5e5+5;
int N;
struct Seg {
int seg[MXN<<2];
Seg() {
fill(seg, seg+(MXN<<2), -2e9-7);
}
void upd(int p, int x, int l=0, int r=N, int id=1) {
seg[id] = max(seg[id], x);
if(r-l == 1) return;
p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
}
int get(int s, int e, int l=0, int r=N, int id=1) {
if(s>=r || l>=e) return -2e9-7;
if(s<=l && r<=e) return seg[id];
return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
} seg[2];
vector<int> cmp;
int GI(int x) { return lower_bound(all(cmp), x)-cmp.begin(); }
int n, ans;
pii a[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for(int i=0; i<n; i++) cin >> a[i].Y >> a[i].X, cmp.push_back(a[i].X);
sort(all(cmp));
cmp.resize(unique(all(cmp))-cmp.begin());
N = SZ(cmp);
for(int i=n-1; i>=0; i--) {
// x[j]-x[i] <= E[j]-E[i] -> E[i]-x[i] <= E[j]-x[j]
// x[i]-x[j] <= E[j]-E[i] -> E[i]+x[i] <= E[j]+x[j]
int pos = GI(a[i].X);
if(a[i].Y-a[i].X > seg[0].get(pos, N) && a[i].Y+a[i].X > seg[1].get(0, pos)) {
ans++;
seg[0].upd(pos, a[i].Y-a[i].X);
seg[1].upd(pos, a[i].Y+a[i].X);
}
}
cout << ans << '\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... |