#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto edu:v)cout<<edu.fst<<","<<edu.snd<<" "; cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
//a
int main(){FIN;
ll n; cin>>n;
vector<ii>a(n),b;
fore(i,0,n)cin>>a[i].fst>>a[i].snd;
sort(ALL(a));
fore(i,0,n){
if(SZ(b)&&b.back().fst==a[i].fst)b.pop_back();
b.pb(a[i]);
}
// cout<<SZ(b)<<"\n"; //sb1
a=b; n=SZ(a);
set<ii>bet;
set<ll>st;
fore(i,0,n)bet.insert({a[i].snd,i}),st.insert(i);
ll res=0;
while(SZ(st)){
res++;
ll p=prev(bet.end())->snd;
vector<ll>pop={p};
for(auto it=st.lower_bound(p);it!=st.begin();){
it--;
ll i=*it;
if(!(abs(a[i].fst-a[p].fst)<=a[p].snd-a[i].snd))break;
pop.pb(i);
}
for(auto it=++st.lower_bound(p);it!=st.end();it++){
ll i=*it;
if(!(abs(a[i].fst-a[p].fst)<=a[p].snd-a[i].snd))break;
pop.pb(i);
}
for(auto i:pop)bet.erase({a[i].snd,i}),st.erase(i);
}
cout<<res<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
91 ms |
18380 KB |
Output is correct |
3 |
Correct |
78 ms |
14796 KB |
Output is correct |
4 |
Correct |
102 ms |
12884 KB |
Output is correct |
5 |
Correct |
55 ms |
8748 KB |
Output is correct |
6 |
Correct |
418 ms |
70072 KB |
Output is correct |
7 |
Correct |
234 ms |
40388 KB |
Output is correct |
8 |
Correct |
110 ms |
13780 KB |
Output is correct |
9 |
Correct |
85 ms |
13140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
548 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 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 |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
548 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 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 |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
91 ms |
18380 KB |
Output is correct |
3 |
Correct |
78 ms |
14796 KB |
Output is correct |
4 |
Correct |
102 ms |
12884 KB |
Output is correct |
5 |
Correct |
55 ms |
8748 KB |
Output is correct |
6 |
Correct |
418 ms |
70072 KB |
Output is correct |
7 |
Correct |
234 ms |
40388 KB |
Output is correct |
8 |
Correct |
110 ms |
13780 KB |
Output is correct |
9 |
Correct |
85 ms |
13140 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
548 KB |
Output is correct |
13 |
Correct |
0 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 |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
492 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
519 ms |
51164 KB |
Output is correct |
37 |
Correct |
682 ms |
65544 KB |
Output is correct |
38 |
Correct |
946 ms |
75956 KB |
Output is correct |
39 |
Correct |
562 ms |
52928 KB |
Output is correct |
40 |
Correct |
853 ms |
74620 KB |
Output is correct |
41 |
Correct |
652 ms |
61356 KB |
Output is correct |
42 |
Correct |
436 ms |
62432 KB |
Output is correct |
43 |
Correct |
471 ms |
78820 KB |
Output is correct |
44 |
Correct |
457 ms |
79404 KB |
Output is correct |
45 |
Correct |
420 ms |
73796 KB |
Output is correct |