Submission #984765

#	Time	Username	Problem	Language	Result	Execution time	Memory
984765		qwerasdfzxcl	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3028 ms	299816 KiB

circle_selection

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
constexpr int INF = 1e9 + 100, CHK = 2;
 
struct Circle{
	int x, y, r, i, xl, xr;
	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;
 
	void init(int n){
		sz = n;
		for (int i=0;i<sz*2;i++){
			tree[i][-INF] = 0;
			tree[i][INF] = 0;
		}
	}
 
	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){
			iter0[pt] = tree[node].lower_bound(y);
			iter[pt] = iter0[pt];
			buf[pt] = iter[pt]->first;
			pt++;
		}
 
		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);
			
			iter[idx]++;
			buf[idx] = iter[idx]->first;
		}
 
		return ret;
 
	}
 
	int queryD(int i){
		for (int i=0;i<pt;i++){
			iter[i] = prev(iter0[i]);
			buf[i] = iter[i]->first;
		}
 
		int ret = i;
 
		for (int _=0;_<CHK;_++){
			int idx = max_element(buf, buf+pt) - buf;
			if (buf[idx]==-INF) break;

			if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);

			iter[idx]--;			
			buf[idx] = iter[idx]->first;
		}
 
		return ret;
	}
}tree;
 
int calc(int x, int i){
	int ret = i;
	ret = min(ret, tree.queryU(x, C[i].y, i));
	ret = min(ret, tree.queryD(i));
 
	return ret;
}
 
int main(){
	int n;
	scanf("%d", &n);
 
	vector<int> X;
	for (int i=1;i<=n;i++){
		scanf("%d %d %d", &C[i].x, &C[i].y, &C[i].r);
		X.push_back(C[i].x - C[i].r);
		X.push_back(C[i].x + C[i].r);
 
		C[i].i = i;
	}
 
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i=1;i<=n;i++){
		C[i].xl = lower_bound(X.begin(), X.end(), C[i].x - C[i].r) - X.begin();
		C[i].xr = lower_bound(X.begin(), X.end(), C[i].x + C[i].r) - X.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].y, i);
 
		ans[C[i].i] = C[ans[C[i].i]].i;
	}
 
	for (int i=1;i<=n;i++) printf("%d ", ans[i]);
	printf("\n");
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%d %d %d", &C[i].x, &C[i].y, &C[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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