Submission #253165

#	Time	Username	Problem	Language	Result	Execution time	Memory
253165		Saboon	Circle selection (APIO18_circle_selection)	C++14	87 / 100	3069 ms	60852 KiB

circle_selection

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

set<pair<ll,ll>> s[maxn];
ll c[maxn], r[maxn];
poll p[maxn];

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

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

int main(){
	ios_base::sync_with_stdio(false);
	ll n;
	cin >> n;
	vector<ll> a;
	vector<pair<ll,ll>> larger;
	for (ll i = 1; i <= n; i++){
		ll x, y;
		cin >> x >> y >> r[i];
		p[i] = poll(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 (ll i = 1; i <= n; i++){
		ll 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){
		ll idx = -it.second;
		if (c[idx] != 0)
			continue;
		ll x = p[idx].real(), y = p[idx].imag();
		ll lef = lower_bound(a.begin(), a.end(), x-2*r[idx])-a.begin();
		ll rig = upper_bound(a.begin(), a.end(), x+2*r[idx])-a.begin();
		for (ll i = lef; i < rig; i++){
			vector<ll> dels;
			for (auto j = s[i].lower_bound(make_pair(y-2*r[idx],0)); j != s[i].end(); j ++){
				ll then = (*j).second;
				if (abs(p[then].imag()-p[idx].imag()) > 2*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){
				ll x = lower_bound(a.begin(), a.end(), p[j].real()) - a.begin();
				s[x].erase({p[j].imag(),j});
			}
		}
	}
	for (ll 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