#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
const int inf = 2e9;
struct Segtree {
vector<int> tree;
int _n;
Segtree() {}
Segtree(int N): tree(4 * N, -inf), _n(N) {}
void update(int pos, int val){
update(1, 0, _n - 1, pos, val);
}
void update(int i, int l, int r, int pos, int val){
if (l == pos && r == pos){
tree[i] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(i<<1, l, mid, pos, val);
else update(i<<1|1, mid+1, r, pos, val);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
int get(int tl, int tr){
return get(1, 0, _n - 1, tl, tr);
}
int get(int i, int l, int r, int tl, int tr){
if (tl <= l && r <= tr) return tree[i];
if (tl > r || tr < l) return -inf;
int mid = (l + r) >> 1;
int resl = get(i<<1, l, mid, tl, tr);
int resr = get(i<<1|1, mid+1, r, tl, tr);
return max(resl, resr);
}
};
int n;
vector<int> X, E;
vector<int> order, pos;
void main_program(){
cin >> n;
X.resize(n);
E.resize(n);
order.resize(n);
pos.resize(n);
for (int i = 0; i < n; i++){
cin >> X[i] >> E[i];
}
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y){
return X[x] < X[y];
});
for (int i = 0; i < n; i++) pos[order[i]] = i;
vector<int> vec(n);
iota(vec.begin(), vec.end(), 0);
sort(vec.begin(), vec.end(), [&](int x, int y){
return E[x] > E[y];
});
int res = 0;
Segtree st_delta(n), st_sum(n);
for (auto idx: vec){
bool alr = false;
if (st_delta.get(pos[idx], n-1) >= E[idx] - X[idx]) alr = true;
if (st_sum.get(0, pos[idx]) >= E[idx] + X[idx]) alr = true;
if (alr) continue;
res++;
st_delta.update(pos[idx], E[idx] - X[idx]);
st_sum.update(pos[idx], E[idx] + X[idx]);
}
cout << res << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
93 ms |
9364 KB |
Output is correct |
3 |
Correct |
130 ms |
13140 KB |
Output is correct |
4 |
Correct |
301 ms |
33024 KB |
Output is correct |
5 |
Correct |
120 ms |
23416 KB |
Output is correct |
6 |
Correct |
482 ms |
35160 KB |
Output is correct |
7 |
Correct |
386 ms |
35432 KB |
Output is correct |
8 |
Correct |
303 ms |
35652 KB |
Output is correct |
9 |
Correct |
203 ms |
35480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
504 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
504 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
488 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
93 ms |
9364 KB |
Output is correct |
3 |
Correct |
130 ms |
13140 KB |
Output is correct |
4 |
Correct |
301 ms |
33024 KB |
Output is correct |
5 |
Correct |
120 ms |
23416 KB |
Output is correct |
6 |
Correct |
482 ms |
35160 KB |
Output is correct |
7 |
Correct |
386 ms |
35432 KB |
Output is correct |
8 |
Correct |
303 ms |
35652 KB |
Output is correct |
9 |
Correct |
203 ms |
35480 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
504 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
460 KB |
Output is correct |
27 |
Correct |
0 ms |
352 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
488 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
245 ms |
23584 KB |
Output is correct |
37 |
Correct |
371 ms |
30124 KB |
Output is correct |
38 |
Correct |
411 ms |
35592 KB |
Output is correct |
39 |
Correct |
423 ms |
32496 KB |
Output is correct |
40 |
Correct |
416 ms |
35412 KB |
Output is correct |
41 |
Correct |
465 ms |
35540 KB |
Output is correct |
42 |
Correct |
361 ms |
35420 KB |
Output is correct |
43 |
Correct |
333 ms |
34616 KB |
Output is correct |
44 |
Correct |
322 ms |
35640 KB |
Output is correct |
45 |
Correct |
449 ms |
31724 KB |
Output is correct |