Submission #984777

#	Time	Username	Problem	Language	Result	Execution time	Memory
984777		qwerasdfzxcl	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1901 ms	156856 KiB

circle_selection

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
 
using namespace std;
typedef long long ll;
 
constexpr int INF = 1e9 + 100, CHK = 2;
 
struct Circle{
	int x, y, r, i, xl, xr, yy;
	Circle(){}
 
	bool operator < (const Circle &C) const{
		if (r==C.r) return i < C.i;
		return r > C.r;
	}
}C[300300];
int ans[300300];
 
int ok(int i, int j){
	ll d = (ll)(C[i].x-C[j].x) * (C[i].x-C[j].x) + (ll)(C[i].y-C[j].y) * (C[i].y-C[j].y);
	ll r = (ll)(C[i].r + C[j].r) * (C[i].r + C[j].r);
	return d <= r;
}
 
struct Seg{
 
	int sz;
	map<int, int> tree[1201200];
 
	map<int, int>::iterator iter0[30], iter[30];
	int T[30], buf[30], pt, py = INF;
 
	void init(int n){
		sz = n;
	}
 
	void update(int l, int r, int y, int i){
		r++;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1){
				tree[l][y] = i;
				l++;
			}
			if (r&1){
				--r;
				tree[r][y] = i;
			}
		}
	}
 
	int queryU(int x, int y, int i){
		pt = 0;
		for (int node=x+sz;node>0;node>>=1){
			if (y!=py || T[pt] != node) iter0[pt] = tree[node].lower_bound(y);
			iter[pt] = iter0[pt];
			T[pt] = node;
			buf[pt] = (iter[pt]==tree[T[pt]].end())?INF:iter[pt]->first;
			pt++;
		}
 
		py = y;
 
		int ret = i;
 
		for (int _=0;_<CHK;_++){
			int idx = min_element(buf, buf+pt) - buf;
			if (buf[idx]==INF) break;
			if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
 
			if (_+1 == CHK) break;
			
			iter[idx]++;
			buf[idx] = (iter[idx]==tree[T[idx]].end())?INF:iter[idx]->first;
		}
 
		return ret;
 
	}
 
	int queryD(int i){
		for (int i=0;i<pt;i++){
			iter[i] = iter0[i];
			buf[i] = (iter[i]==tree[T[i]].begin())?(-INF):prev(iter[i])->first;
		}
 
		int ret = i;
 
		for (int _=0;_<CHK;_++){
			int idx = max_element(buf, buf+pt) - buf;
			if (buf[idx]==-INF) break;
			
			iter[idx]--;
			if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
			
			buf[idx] = (iter[idx]==tree[T[idx]].begin())?(-INF):prev(iter[idx])->first;
		}
 
		return ret;
	}
}tree;
 
int calc(int x, int i){
	int ret = i;
	ret = min(ret, tree.queryU(x, C[i].yy, i));
	ret = min(ret, tree.queryD(i));
 
	return ret;
}
 
int main(){
	ll a = 32154, b = 38591;

	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	vector<long double> X;
	vector<ll> Y;
	long double t = sqrtl(a*a + b*b);

	for (int i=1;i<=n;i++){
		cin >> C[i].x >> C[i].y >> C[i].r;
		X.push_back((a*C[i].x+b*C[i].y) - t*C[i].r);
		X.push_back((a*C[i].x+b*C[i].y) + t*C[i].r);
		Y.push_back(-b*C[i].x+a*C[i].y);
 
		C[i].i = i;
	}
 
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for (int i=1;i<=n;i++){
		C[i].xl = lower_bound(X.begin(), X.end(), (a*C[i].x+b*C[i].y) - t*C[i].r) - X.begin();
		C[i].xr = lower_bound(X.begin(), X.end(), (a*C[i].x+b*C[i].y) + t*C[i].r) - X.begin();
		C[i].yy = lower_bound(Y.begin(), Y.end(), -b*C[i].x+a*C[i].y) - Y.begin();
	}
 
	sort(C+1, C+n+1);
	tree.init(X.size());
 
	for (int i=1;i<=n;i++){
		ans[C[i].i] = min(calc(C[i].xl, i), calc(C[i].xr, i));
		if (ans[C[i].i]==i) tree.update(C[i].xl, C[i].xr, C[i].yy, i);
 
		ans[C[i].i] = C[ans[C[i].i]].i;
	}
 
	for (int i=1;i<=n;i++) printf("%d ", ans[i]);
	printf("\n");
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13