#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
void unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
}
};
bool comp(pair<int,int> a,pair<int,int> b){
if(a.s!=b.s) return a.s<b.s;
return a.f<b.f;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin>>n;
vector<pair<int,int>> num(n);
for(int i=0;i<n;i++){
int x,e;
cin>>x>>e;
num[i]={x,e};
}
sort(all(num),comp);
multiset<pair<int,int>> vec;
int ans=0;
for(int i=n-1;i>=0;i--){
auto it=vec.lower_bound({num[i].s-num[i].f,0});
if(it==vec.end()){
vec.insert({num[i].s-num[i].f,i});
ans++;
}
else{
auto id=(*it).s;
if(abs(num[id].f-num[i].f)>(num[id].s-num[i].s)){
vec.insert({num[i].s-num[i].f,i});
ans++;
}
}
}
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
57 ms |
9176 KB |
Output is correct |
3 |
Correct |
65 ms |
8764 KB |
Output is correct |
4 |
Correct |
125 ms |
13004 KB |
Output is correct |
5 |
Correct |
62 ms |
9124 KB |
Output is correct |
6 |
Correct |
235 ms |
34644 KB |
Output is correct |
7 |
Correct |
234 ms |
24052 KB |
Output is correct |
8 |
Correct |
126 ms |
14068 KB |
Output is correct |
9 |
Correct |
102 ms |
14028 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 |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
320 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 |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
0 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 |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
320 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 |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
288 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
57 ms |
9176 KB |
Output is correct |
3 |
Correct |
65 ms |
8764 KB |
Output is correct |
4 |
Correct |
125 ms |
13004 KB |
Output is correct |
5 |
Correct |
62 ms |
9124 KB |
Output is correct |
6 |
Correct |
235 ms |
34644 KB |
Output is correct |
7 |
Correct |
234 ms |
24052 KB |
Output is correct |
8 |
Correct |
126 ms |
14068 KB |
Output is correct |
9 |
Correct |
102 ms |
14028 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
320 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 |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
288 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
336 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
368 KB |
Output is correct |
36 |
Correct |
103 ms |
9288 KB |
Output is correct |
37 |
Correct |
133 ms |
11804 KB |
Output is correct |
38 |
Correct |
146 ms |
13808 KB |
Output is correct |
39 |
Correct |
147 ms |
10848 KB |
Output is correct |
40 |
Correct |
147 ms |
13812 KB |
Output is correct |
41 |
Correct |
165 ms |
13808 KB |
Output is correct |
42 |
Correct |
138 ms |
13816 KB |
Output is correct |
43 |
Correct |
154 ms |
18892 KB |
Output is correct |
44 |
Correct |
145 ms |
13904 KB |
Output is correct |
45 |
Correct |
228 ms |
33384 KB |
Output is correct |