#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int INF=1000000000;
const int N=500000;
pii seg[2*N];
int eminusx[N];
int nx[N];
int n;
void build(){
for(int i=0;i<n;i++){
seg[i+n]=mp(eminusx[i],i);
}
for(int i=n-1;i>0;i--){
seg[i]=max(seg[2*i],seg[2*i+1]);
}
}
int query(int l,int r){
l+=n;
r+=n;
pii ans=mp(-INF,-INF);
while(l<r){
if(l&1){
ans=max(ans,seg[l]);
l++;
}
if(r&1){
r--;
ans=max(ans,seg[r]);
}
l>>=1;
r>>=1;
}
return ans.second;
}
void solve(){
cin >>n;
int x[n];
int e[n];
for(int i=0;i<n;i++){
cin >> x[i] >> e[i];
}
vector<pii> tosort;
for(int i=0;i<n;i++) tosort.push_back(mp(e[i]+x[i],e[i]-x[i]));
sort(tosort.begin(),tosort.end());
for(int i=0;i<n;i++) eminusx[i]=tosort[i].second;
build();
int cnt=0;
int ind=-1;
while(ind!=n-1){
ind=query(ind+1,n);
cnt++;
}
cout << cnt << "\n";
}
signed main(){
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
t=1;
//cin >> t;
while(t--) solve();
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
46 ms |
8736 KB |
Output is correct |
3 |
Correct |
56 ms |
11464 KB |
Output is correct |
4 |
Correct |
113 ms |
18776 KB |
Output is correct |
5 |
Correct |
60 ms |
15900 KB |
Output is correct |
6 |
Correct |
154 ms |
19836 KB |
Output is correct |
7 |
Correct |
162 ms |
19820 KB |
Output is correct |
8 |
Correct |
132 ms |
19928 KB |
Output is correct |
9 |
Correct |
109 ms |
19844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
2 ms |
4560 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4440 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
2 ms |
4560 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4440 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
46 ms |
8736 KB |
Output is correct |
3 |
Correct |
56 ms |
11464 KB |
Output is correct |
4 |
Correct |
113 ms |
18776 KB |
Output is correct |
5 |
Correct |
60 ms |
15900 KB |
Output is correct |
6 |
Correct |
154 ms |
19836 KB |
Output is correct |
7 |
Correct |
162 ms |
19820 KB |
Output is correct |
8 |
Correct |
132 ms |
19928 KB |
Output is correct |
9 |
Correct |
109 ms |
19844 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4440 KB |
Output is correct |
13 |
Correct |
1 ms |
4696 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4440 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
2 ms |
4560 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
1 ms |
4444 KB |
Output is correct |
29 |
Correct |
1 ms |
4444 KB |
Output is correct |
30 |
Correct |
1 ms |
4444 KB |
Output is correct |
31 |
Correct |
1 ms |
4444 KB |
Output is correct |
32 |
Correct |
1 ms |
4444 KB |
Output is correct |
33 |
Correct |
1 ms |
4440 KB |
Output is correct |
34 |
Correct |
2 ms |
4444 KB |
Output is correct |
35 |
Correct |
1 ms |
4440 KB |
Output is correct |
36 |
Correct |
88 ms |
20948 KB |
Output is correct |
37 |
Correct |
106 ms |
21944 KB |
Output is correct |
38 |
Correct |
137 ms |
25500 KB |
Output is correct |
39 |
Correct |
122 ms |
23464 KB |
Output is correct |
40 |
Correct |
129 ms |
25280 KB |
Output is correct |
41 |
Correct |
129 ms |
25308 KB |
Output is correct |
42 |
Correct |
141 ms |
25344 KB |
Output is correct |
43 |
Correct |
133 ms |
24472 KB |
Output is correct |
44 |
Correct |
154 ms |
25168 KB |
Output is correct |
45 |
Correct |
147 ms |
23168 KB |
Output is correct |