#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 5e5 + 5;
int n, pot = 1;
int x[maxn];
int e[maxn];
int T1[maxn * 4], T2[maxn * 4];
map<int, int> pos;
vector<ii> v;
void update1(int x, int v) {
x += pot;
T1[x] = min(T1[x], v);
x >>= 1;
while(x > 0)
T1[x] = min(T1[x * 2], T1[x * 2 + 1]), x >>= 1;
}
void update2(int x, int v) {
x += pot;
T2[x] = max(T2[x], v);
x >>= 1;
while(x > 0)
T2[x] = max(T2[x * 2], T2[x * 2 + 1]), x >>= 1;
}
int query1(int x, int lo, int hi, int a, int b) {
if(hi < a || b < lo) return 2e9 + 1;
if(a <= lo && hi <= b) return T1[x];
int mid = (lo + hi) / 2;
int L = query1(x * 2, lo, mid, a, b);
int R = query1(x * 2 + 1, mid + 1, hi, a, b);
return min(L, R);
}
int query2(int x, int lo, int hi, int a, int b) {
if(hi < a || b < lo) return -2e9 - 1;
if(a <= lo && hi <= b) return T2[x];
int mid = (lo + hi) / 2;
int L = query2(x * 2, lo, mid, a, b);
int R = query2(x * 2 + 1, mid + 1, hi, a, b);
return max(L, R);
}
int check(int i, int j) {
return abs(x[i] - x[j]) <= e[i] - e[j];
}
int main() {
scanf("%d", &n);
for(int i = 0;i < n;i++)
scanf("%d%d", x + i, e + i);
while(pot < n) pot <<= 1;
for(int i = 1;i < (pot << 1);i++)
T1[i] = 2e9 + 1, T2[i] = -2e9 - 1;
for(int i = 0;i < n;i++)
v.pb({e[i], x[i]});
sort(all(v));
reverse(all(v));
set<int> s;
for(int i = 0;i < n;i++)
s.insert(x[i]);
vector<int> v1(all(s));
int m = (int)v1.size();
for(int i = 0;i < m;i++)
pos[v1[i]] = i;
int ans = 0;
for(ii p : v) {
int flag = 1;
int A = query1(1, 0, pot - 1, pos[p.y], m - 1);
int B = query2(1, 0, pot - 1, 0, pos[p.y]);
if(p.y - p.x >= A) flag = 0;
if(p.y + p.x <= B) flag = 0;
ans += flag;
if(flag) {
update1(pos[p.y], p.y - p.x);
update2(pos[p.y], p.y + p.x);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d%d", x + i, e + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
165 ms |
17668 KB |
Output is correct |
3 |
Correct |
204 ms |
18000 KB |
Output is correct |
4 |
Correct |
279 ms |
20828 KB |
Output is correct |
5 |
Correct |
138 ms |
21696 KB |
Output is correct |
6 |
Correct |
861 ms |
70024 KB |
Output is correct |
7 |
Correct |
540 ms |
47144 KB |
Output is correct |
8 |
Correct |
283 ms |
26508 KB |
Output is correct |
9 |
Correct |
205 ms |
26344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
440 KB |
Output is correct |
21 |
Correct |
1 ms |
308 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
3 ms |
444 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
165 ms |
17668 KB |
Output is correct |
3 |
Correct |
204 ms |
18000 KB |
Output is correct |
4 |
Correct |
279 ms |
20828 KB |
Output is correct |
5 |
Correct |
138 ms |
21696 KB |
Output is correct |
6 |
Correct |
861 ms |
70024 KB |
Output is correct |
7 |
Correct |
540 ms |
47144 KB |
Output is correct |
8 |
Correct |
283 ms |
26508 KB |
Output is correct |
9 |
Correct |
205 ms |
26344 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
440 KB |
Output is correct |
30 |
Correct |
1 ms |
308 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
3 ms |
444 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
468 KB |
Output is correct |
35 |
Correct |
2 ms |
468 KB |
Output is correct |
36 |
Correct |
665 ms |
52484 KB |
Output is correct |
37 |
Correct |
941 ms |
64772 KB |
Output is correct |
38 |
Correct |
1210 ms |
74964 KB |
Output is correct |
39 |
Correct |
861 ms |
53904 KB |
Output is correct |
40 |
Correct |
1158 ms |
73500 KB |
Output is correct |
41 |
Correct |
952 ms |
62748 KB |
Output is correct |
42 |
Correct |
728 ms |
62768 KB |
Output is correct |
43 |
Correct |
846 ms |
73912 KB |
Output is correct |
44 |
Correct |
834 ms |
74900 KB |
Output is correct |
45 |
Correct |
914 ms |
70496 KB |
Output is correct |