#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
struct segtree{
vector<ll> arr;
int n;
bool type = 0;
void init(int s,bool t){
type = t;
if(type) arr.resize(2*s,-1e10);
else arr.resize(2*s,1e10);
n = s;
}
ll minmax(ll a,ll b){
return (type)?(max(a,b)):(min(a,b));
}
void modify(int ind,ll v){
ind+=n;
while(ind){
//cout<<type<<"|"<<ind<<":"<<arr[ind]<<"v.s"<<v<<": win:";
arr[ind] = minmax(arr[ind],v);
//cout<<arr[ind]<<"\n";
ind>>=1;
}
}
ll query(int l,int r){
l+=n;r+=n;
ll ans = (type)?(-1e10):(1e10);
while(r>l){
if(l&1) ans = minmax(ans,arr[l++]);
if(r&1) ans = minmax(ans,arr[--r]);
l>>=1;r>>=1;
}
return ans;
}
};
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
vector<int> x(n);
vector<int> e(n);
vector<int> d(n);
vector<int> order(n);
for(int i=0;i<n;i++){
cin>>x[i]>>e[i];
d[i]=x[i];
order[i]=i;
}
sort(d.begin(),d.end());
d.resize(unique(d.begin(),d.end())-d.begin());
sort(order.begin(),order.end(),[&](const int a,const int b){return e[a]>e[b];});
segtree pre;segtree suf;
pre.init(d.size(),1);
suf.init(d.size(),0);
int cnt = 0;
int rb = d.size();
for(int i=0;i<n;i++){
int p = order[i];
int loc = lower_bound(d.begin(),d.end(),x[p])-d.begin();
ll premax = pre.query(0,loc+1);
ll sufmin = suf.query(loc,rb);
//cout<<premax<<" "<<sufmin<<"\n";
if(premax>=x[p]+e[p] || sufmin<=x[p]-e[p]) continue;
else{
cnt++;
pre.modify(loc,x[p]+e[p]);
suf.modify(loc,x[p]-e[p]);
}
//cout<<pre.query(0,rb)<<" "<<suf.query(0,rb)<<"\n";
}
cout<<cnt<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
83 ms |
8344 KB |
Output is correct |
3 |
Correct |
105 ms |
8988 KB |
Output is correct |
4 |
Correct |
205 ms |
16688 KB |
Output is correct |
5 |
Correct |
68 ms |
11788 KB |
Output is correct |
6 |
Correct |
450 ms |
31568 KB |
Output is correct |
7 |
Correct |
304 ms |
24536 KB |
Output is correct |
8 |
Correct |
236 ms |
18020 KB |
Output is correct |
9 |
Correct |
95 ms |
17916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
316 KB |
Output is correct |
11 |
Correct |
1 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 |
0 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 |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
316 KB |
Output is correct |
11 |
Correct |
1 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 |
0 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 |
0 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 |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
328 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
83 ms |
8344 KB |
Output is correct |
3 |
Correct |
105 ms |
8988 KB |
Output is correct |
4 |
Correct |
205 ms |
16688 KB |
Output is correct |
5 |
Correct |
68 ms |
11788 KB |
Output is correct |
6 |
Correct |
450 ms |
31568 KB |
Output is correct |
7 |
Correct |
304 ms |
24536 KB |
Output is correct |
8 |
Correct |
236 ms |
18020 KB |
Output is correct |
9 |
Correct |
95 ms |
17916 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 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 |
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 |
316 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 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 |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
328 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
252 ms |
22400 KB |
Output is correct |
37 |
Correct |
342 ms |
28388 KB |
Output is correct |
38 |
Correct |
434 ms |
33512 KB |
Output is correct |
39 |
Correct |
374 ms |
24672 KB |
Output is correct |
40 |
Correct |
431 ms |
33000 KB |
Output is correct |
41 |
Correct |
410 ms |
29520 KB |
Output is correct |
42 |
Correct |
283 ms |
29496 KB |
Output is correct |
43 |
Correct |
300 ms |
32460 KB |
Output is correct |
44 |
Correct |
311 ms |
33604 KB |
Output is correct |
45 |
Correct |
380 ms |
29612 KB |
Output is correct |