#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
void solve(int tc) {
int n;
cin>>n;
set<pair<int,int>>st;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
st.insert({x,y});
}
vector<pair<int,int>>vt;
for(pair<int,int>k:st)vt.push_back(k);
int l=vt.size();
bool have[l];
for(int i=0;i<l;i++)have[i]=0;
int ma=0;
for(int i=0;i<l;i++){
if(ma>=vt[i].first+vt[i].second)have[i]=1;
ma=max(ma,vt[i].first+vt[i].second);
}
int mi=1e18;
for(int i=l-1;i>=0;i--){
if(mi<=vt[i].first-vt[i].second)have[i]=1;
mi=min(mi,vt[i].first-vt[i].second);
}
int s=0;
for(int i=0;i<l;i++)s+=have[i];
cout<<l-s<<'\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
60 ms |
12184 KB |
Output is correct |
3 |
Correct |
71 ms |
10740 KB |
Output is correct |
4 |
Correct |
116 ms |
9676 KB |
Output is correct |
5 |
Correct |
50 ms |
6564 KB |
Output is correct |
6 |
Correct |
463 ms |
46248 KB |
Output is correct |
7 |
Correct |
264 ms |
27692 KB |
Output is correct |
8 |
Correct |
130 ms |
10460 KB |
Output is correct |
9 |
Correct |
74 ms |
10060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 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 |
0 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 |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
324 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
372 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
60 ms |
12184 KB |
Output is correct |
3 |
Correct |
71 ms |
10740 KB |
Output is correct |
4 |
Correct |
116 ms |
9676 KB |
Output is correct |
5 |
Correct |
50 ms |
6564 KB |
Output is correct |
6 |
Correct |
463 ms |
46248 KB |
Output is correct |
7 |
Correct |
264 ms |
27692 KB |
Output is correct |
8 |
Correct |
130 ms |
10460 KB |
Output is correct |
9 |
Correct |
74 ms |
10060 KB |
Output is correct |
10 |
Correct |
1 ms |
324 KB |
Output is correct |
11 |
Correct |
0 ms |
212 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 |
0 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
324 KB |
Output is correct |
31 |
Correct |
1 ms |
336 KB |
Output is correct |
32 |
Correct |
1 ms |
372 KB |
Output is correct |
33 |
Correct |
1 ms |
336 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
255 ms |
35836 KB |
Output is correct |
37 |
Correct |
354 ms |
43272 KB |
Output is correct |
38 |
Correct |
436 ms |
49628 KB |
Output is correct |
39 |
Correct |
458 ms |
46716 KB |
Output is correct |
40 |
Correct |
492 ms |
49664 KB |
Output is correct |
41 |
Correct |
486 ms |
49724 KB |
Output is correct |
42 |
Correct |
435 ms |
49700 KB |
Output is correct |
43 |
Correct |
470 ms |
48684 KB |
Output is correct |
44 |
Correct |
502 ms |
49780 KB |
Output is correct |
45 |
Correct |
416 ms |
45788 KB |
Output is correct |