#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vector<pii> arr;
// abs(xi - xj) <= yi - yj -> we place on i
// let xi >= xj
// yj - xj <= yi - xi
// let xi < xj
// xj + yj <= yi + xi
int tree_levo[4 * 200100], tree_desno[4 * 200100];
// tree_levo - check left side
// tree_desno - check right side;
void build(int node, int l, int r){
if(l == r){
tree_levo[node] = -1e9;
tree_desno[node] = -1e9;
}
else{
int mid = (l + r) / 2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
tree_levo[node] = max(tree_levo[node*2], tree_levo[node*2+1]);
tree_desno[node] = max(tree_desno[node*2], tree_desno[node*2+1]);
}
}
void update_levo(int node, int l, int r, int pos, int set){
if(l == r) tree_levo[node] = set;
else{
int mid = (l + r) / 2;
if(pos <= mid) update_levo(node*2, l, mid, pos, set);
else update_levo(node*2+1, mid+1, r, pos, set);
tree_levo[node] = max(tree_levo[node*2], tree_levo[node*2+1]);
}
}
void update_desno(int node, int l, int r, int pos, int set){
if(l == r) tree_desno[node] = set;
else{
int mid = (l + r) / 2;
if(pos <= mid) update_desno(node*2, l, mid, pos, set);
else update_desno(node*2+1, mid+1, r, pos, set);
tree_desno[node] = max(tree_desno[node*2], tree_desno[node*2+1]);
}
}
int query_levo(int node, int l, int r, int L, int R){
if(r < L || l > R) return -1e9;
if(L <= l && r <= R) return tree_levo[node];
int mid = (l + r) / 2;
int left = query_levo(node*2, l, mid, L, R);
int right = query_levo(node*2+1, mid+1, r, L, R);
return max(left, right);
}
int query_desno(int node, int l, int r, int L, int R){
if(r < L || l > R) return -1e9;
if(L <= l && r <= R) return tree_desno[node];
int mid = (l + r) / 2;
int left = query_desno(node*2, l, mid, L, R);
int right = query_desno(node*2+1, mid+1, r, L, R);
return max(left, right);
}
//1 1 -> 0
//3 2 -> 1
//4 3 -> 2
//5 1 -> 3
// 4 3
// update_desno na pozicija 2 -> -1
// update_levo na pozicija 2 -> 7
// 3 2
// query_desno za (0, 1) ke dade -1
// query_levo za (2, 3) ke dade 7
// 5 1
// 1 1
int main(){
cin>>n;
arr.resize(n);
priority_queue<pii> pq;
for(int i = 0; i < n; i++){
cin>>arr[i].first>>arr[i].second;
// pq.push(mp(arr[i].second, i));
}
sort(arr.begin(), arr.end());
for(int i = 0; i < n; i++){
pq.push(mp(arr[i].second, i));
}
build(1, 0, n-1);
bool vis[n];
memset(vis, false, sizeof vis);
int ans = 0;
while(!pq.empty()){
pii here = pq.top();
pq.pop();
int pos = here.second;
// cout<<pos<<endl;
// cout<<query_levo(1, 0, n-1, 0, pos-1)<<" "<<arr[pos].second + arr[pos].first<<endl;
// cout<<query_desno(1, 0, n-1, pos+1, n-1)<<" "<<arr[pos].second - arr[pos].first<<endl;
if(query_levo(1, 0, n-1, 0, pos-1) >= arr[pos].second + arr[pos].first) continue;
else if(query_desno(1, 0, n-1, pos+1, n-1) >= arr[pos].second - arr[pos].first) continue;
else{
// cout<<pos<<endl;
ans++;
}
update_levo(1, 0, n-1, pos, arr[pos].second + arr[pos].first);
update_desno(1, 0, n-1, pos, arr[pos].second - arr[pos].first);
}
cout<<ans<<endl;
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
76124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2035 ms |
79036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
76124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
