#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
#define INF (1ll<<60)
#define MAX 300000
#define largo 2000000000ll
//para el vector de orden
#define id second
struct xx {
lli x;
lli y;
lli r;
};
struct yy {
lli MIN;
lli lazy;
lli hizq;
lli hder;
};
lli n,cont;
lli res[MAX+2],new_order[MAX+2];
xx circulo[MAX+2];
vector<pll> orden;
vector<yy> stree;
yy trash;
void push(lli pos) {
if (stree[pos].lazy == INF) return;
if (stree[pos].hizq == 0) {
lli a = stree.size();
stree.push_back(trash);
stree.back().MIN = stree[pos].MIN;
stree.push_back(trash);
stree.back().MIN = stree[pos].MIN;
stree[pos].hizq = a;
stree[pos].hder = a+1;
}
stree[stree[pos].hizq].lazy = min(stree[stree[pos].hizq].lazy, stree[pos].lazy);
stree[stree[pos].hder].lazy = min(stree[stree[pos].hder].lazy, stree[pos].lazy);
stree[pos].MIN = min(stree[pos].MIN, stree[pos].lazy);
stree[pos].lazy = INF;
}
lli query(lli pos, lli ini, lli fin, lli l, lli r) {
if (ini > r || fin < l) return 0;
if (l <= ini && fin <= r) return stree[pos].MIN;
//debugsl(ini);
//debugsl(fin);
//debugsl(l);
//debug(r);
lli mitad = (ini+fin)/2;
push(pos);
lli a = query(stree[pos].hizq, ini,mitad,l,r);
lli b = query(stree[pos].hder, mitad+1,fin,l,r);
return min(a, b);
}
void update(lli pos, lli ini, lli fin, lli l, lli r, lli val) {
if (ini > r || fin < l) return;
if (ini == fin) {
stree[pos].MIN = min(stree[pos].MIN, stree[pos].lazy);
stree[pos].MIN = min(stree[pos].MIN, val);
return;
}
if (l <= ini && fin <= r) {
push(pos);
stree[pos].lazy = val;
return;
}
lli mitad = (ini+fin)/2;
push(pos);
update(stree[pos].hizq, ini,mitad,l,r,val);
update(stree[pos].hder, mitad+1,fin,l,r,val);
lli a = stree[ stree[pos].hizq ].MIN;
lli b = stree[ stree[pos].hder ].MIN;
stree[pos].MIN = min(a, b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
trash.MIN = INF;
trash.lazy = INF;
cin >> n;
rep(i,1,n) {
cin >> circulo[i].x >> circulo[i].y >> circulo[i].r;
circulo[i].x += largo;
orden.push_back({-circulo[i].r, i});
}
sort(orden.begin(), orden.end());
stree.push_back(trash);
cont = 1;
new_order[0] = INF;
rep(i, 0, orden.size() - 1) {
//debug(act.id);
lli l = -orden[i].first - orden[i].second;
lli r = -orden[i].first + orden[i].second;
lli a = query(0,0,largo*2,l,r);
//debugsl(l);
//debug(r);
if (a == INF) { //meto mi rango
res[orden[i].second] = orden[i].second;
update(0,0,largo*2,l,r,orden[i].second);
}
else res[orden[i].second] = a;
}
rep(i,1,n) cout << res[i] << ' ';
return 0;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
| ^
circle_selection.cpp:123:5: note: in expansion of macro 'rep'
123 | rep(i, 0, orden.size() - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
254 ms |
15064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
15092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
