Submission #253168

#	Time	Username	Problem	Language	Result	Execution time	Memory
253168		Saboon	Circle selection (APIO18_circle_selection)	C++14	87 / 100	3081 ms	38992 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<int> point;
const int maxn = 3e5 + 20;
const int inf = 1e9;

set<pair<int,int>> s[maxn];
int c[maxn], r[maxn];
point p[maxn];

ll SQ(int x){
	return 1ll*x*x;
}

ll dis(point x, point y){
	return SQ(x.real() - y.real()) + SQ(x.imag() - y.imag());
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a;
	vector<pair<int,int>> larger;
	for (int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y >> r[i];
		p[i] = point(x,y);
		a.push_back(x);
		larger.push_back({r[i],-i});
	}
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(),a.end())-a.begin());
	for (int i = 1; i <= n; i++){
		int x = p[i].real(), y = p[i].imag();
		x = lower_bound(a.begin(), a.end(), x) - a.begin();
		s[x].insert({y,i});
	}
	sort(larger.rbegin(), larger.rend());
	for (auto it : larger){
		int idx = -it.second;
		if (c[idx] != 0)
			continue;
		int x = p[idx].real(), y = p[idx].imag();
		int lef = lower_bound(a.begin(), a.end(), x-2ll*r[idx])-a.begin();
		int rig = upper_bound(a.begin(), a.end(), x+2ll*r[idx])-a.begin();
		for (int i = lef; i < rig; i++){
			vector<int> dels;
			for (auto j = s[i].lower_bound(make_pair(y-2ll*r[idx],0)); j != s[i].end(); j ++){
				int then = (*j).second;
				if (abs(p[then].imag()-p[idx].imag()) > 2ll*r[idx])
					break;
				if (dis(p[idx],p[then]) <= SQ(r[idx]+r[then])){
					c[then] = idx;
					dels.push_back(then);
				}
			}
			for (auto j : dels){
				int x = lower_bound(a.begin(), a.end(), p[j].real()) - a.begin();
				s[x].erase({p[j].imag(),j});
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << c[i] << " \n"[i == n];
}

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