#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,4>pi2;
inline pii combine(pii a, pii b){
//max min
return {max(a.first,b.first),min(a.second,b.second)};
}
struct node{
int s,e,m;
node *l,*r;
pii v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL){
v={LONG_LONG_MIN,LONG_LONG_MAX};
}
inline void inst(){
if(l==NULL)l=new node(s,m);
if(r==NULL)r=new node(m+1,e);
}
void upd(int x, int y){
if(s==e){
v.first=max(v.first,y);
v.second=min(v.second,y);
return;
}
inst();
if(x<=m)l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
pii query(int x, int y){
if(x<=s&&y>=e) return v;
inst();
if(y<=m)return l->query(x,y);
if(x>m)return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
bool cmp(const pii a, const pii b){
return a.second>b.second;
}
void solve(){
int n;
cin >> n;
pii arr[n];
vector<int>v;
for(int x=0;x<n;x++){
cin >> arr[x].first >> arr[x].second;
v.push_back(arr[x].first);
}
v.push_back(0);
v.push_back(LONG_LONG_MAX/3);
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
unordered_map<int,int>dis;
for(int x=0;x<n;x++){
int index=lower_bound(v.begin(),v.end(),arr[x].first)-v.begin();
dis[arr[x].first]=index+1;
}
dis[0]=1;
dis[LONG_LONG_MAX/3]=v.size();
sort(arr,arr+n,cmp);
node left(0,v.size()+10);
node right(0,v.size()+10);
int counter=0;
for(int x=0;x<n;x++){
//check left (range max)
//check right (range min)
int pos=arr[x].first;
pii hold=left.query(dis[0],dis[pos]);
pii hold2=right.query(dis[pos],dis[LONG_LONG_MAX/3]);
if(hold.first>=arr[x].first+arr[x].second||hold2.second<=arr[x].first-arr[x].second){
continue;
}
counter++;
left.upd(dis[arr[x].first],arr[x].first+arr[x].second);
right.upd(dis[arr[x].first],arr[x].first-arr[x].second);
}
cout << counter;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt", "r", stdin);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
265 ms |
37496 KB |
Output is correct |
3 |
Correct |
288 ms |
27200 KB |
Output is correct |
4 |
Correct |
337 ms |
12480 KB |
Output is correct |
5 |
Correct |
81 ms |
11564 KB |
Output is correct |
6 |
Correct |
1503 ms |
145516 KB |
Output is correct |
7 |
Correct |
1102 ms |
85540 KB |
Output is correct |
8 |
Correct |
375 ms |
23224 KB |
Output is correct |
9 |
Correct |
125 ms |
21956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
660 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
265 ms |
37496 KB |
Output is correct |
3 |
Correct |
288 ms |
27200 KB |
Output is correct |
4 |
Correct |
337 ms |
12480 KB |
Output is correct |
5 |
Correct |
81 ms |
11564 KB |
Output is correct |
6 |
Correct |
1503 ms |
145516 KB |
Output is correct |
7 |
Correct |
1102 ms |
85540 KB |
Output is correct |
8 |
Correct |
375 ms |
23224 KB |
Output is correct |
9 |
Correct |
125 ms |
21956 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 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 |
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 |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
660 KB |
Output is correct |
34 |
Correct |
1 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
809 ms |
110708 KB |
Output is correct |
37 |
Correct |
1079 ms |
144140 KB |
Output is correct |
38 |
Correct |
1306 ms |
168304 KB |
Output is correct |
39 |
Correct |
1090 ms |
110612 KB |
Output is correct |
40 |
Correct |
1311 ms |
164260 KB |
Output is correct |
41 |
Correct |
1146 ms |
133160 KB |
Output is correct |
42 |
Correct |
826 ms |
133260 KB |
Output is correct |
43 |
Correct |
965 ms |
167432 KB |
Output is correct |
44 |
Correct |
824 ms |
168272 KB |
Output is correct |
45 |
Correct |
1410 ms |
164652 KB |
Output is correct |