Submission #252532

#TimeUsernameProblemLanguageResultExecution timeMemory
252532shayan_pCircle selection (APIO18_circle_selection)C++14
64 / 100
1947 ms157724 KiB
// And you curse yourself for things you never done #include<bits/stdc++.h> #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10; const ll INF = 1e18; pair<pii, int> p[maxn]; int arr[maxn], ans[maxn]; pii operator - (pii a, pii b){ return {a.F - b.F, a.S - b.S}; } pii operator + (pii a, pii b){ return {a.F + b.F, a.S + b.S}; } ll operator ^ (pii a, pii b){ return 1ll * a.F * b.F + 1ll * a.S * b.S; } bool ok(int i, int j){ return 1ll * (p[j].S + p[i].S) * (p[j].S + p[i].S) >= ((p[i].F - p[j].F) ^ (p[i].F - p[j].F)); } vector<int> vx, vy; vector<int> val, fs; vector<int> stock; void push(int &lst, int x){ fs.PB(lst); lst = sz(val); val.PB(x); } struct node{ map<int, int> mp; void add(int pos, int x){ mp[pos] = x; } void ask(int i){ int pos = p[i].F.S; auto it = mp.lower_bound(pos); if(it != mp.end()) stock.PB(it->S); if(it != mp.begin()) stock.PB(prev(it)->S); } }; struct node2{ node2 *L = 0, *R = 0; node* seg = 0; void add(int f, int s, int pos, int x, int l = 0, int r = sz(vx)-1){ if(f <= vx[l] && vx[r] <= s){ if(!seg) seg = new node(); seg->add(pos, x); return; } if(r-l == 1) return; int mid = (l+r) >> 1; if(max(f, vx[l]) < min(s, vx[mid])){ if(!L) L = new node2(); L->add(f, s, pos, x, l, mid); } if(max(f, vx[mid]) < min(s, vx[r])){ if(!R) R = new node2(); R->add(f, s, pos, x, mid, r); } } void ask(int pos, int pos2, int l = 0, int r = sz(vx)-1){ if(seg) seg->ask(pos2); if(r-l == 1) return; int mid = (l+r) >> 1; if(pos < vx[mid] && L) L->ask(pos, pos2, l, mid); if(vx[mid] <= pos && R) R->ask(pos, pos2, mid, r); } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(); node2* root = new node2(); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> p[i].F.F >> p[i].F.S >> p[i].S; vx.PB(p[i].F.F - p[i].S); vx.PB(p[i].F.F + p[i].S + 1); vy.PB(p[i].F.S - p[i].S); vy.PB(p[i].F.S + p[i].S + 1); arr[i] = i; } auto cmp = [](int i, int j){ return (p[i].S == p[j].S ? i > j : p[i].S < p[j].S); }; sort(arr, arr + n, cmp); sort(vx.begin(), vx.end()); vx.resize( unique(vx.begin(), vx.end()) - vx.begin() ); sort(vy.begin(), vy.end()); vy.resize( unique(vy.begin(), vy.end()) - vy.begin() ); for(int i = n-1; i >= 0; i--){ int I = arr[i]; stock.clear(); for(int w = -1; w <= 1; w++){ if(w != 0) root->ask(p[I].F.F + w * p[I].S, I); // kafie? } for(int id : stock){ if(ok(I, id)){ if(ans[I] == 0 || cmp(ans[I] - 1, id)) ans[I] = id + 1; } } if(ans[I] == 0){ ans[I] = I + 1; root->add(p[I].F.F - p[I].S, p[I].F.F + p[I].S + 1, p[I].F.S, I); } } for(int i = 0; i < n; i++){ cout << ans[i] << " "; } return cout << endl, 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...