Submission #95382

#	Time	Username	Problem	Language	Result	Execution time	Memory
95382		pranjalssh	Circle selection (APIO18_circle_selection)	C++14	37 / 100	3061 ms	244096 KiB

circle_selection

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


const int N = 3e5 + 10;
vi x, y, r;
set<ii> T[4 * N + 10];
vi cmp;
vi par;
void ins(int no, int l, int r, int id) {
	T[no].emplace(y[id], id);
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (x[id] <= cmp[mid]) ins(2 * no, l, mid, id);
	else ins(2 * no + 1, mid + 1, r, id);
}
vector<ii> rem;
inline bool intersect(int i, int j) {
	return (x[i] - x[j]) * 1LL * (x[i] - x[j]) + (y[i] - y[j]) * 1LL * (y[i] - y[j]) <= (r[i] + r[j]) * 1LL * (r[i] + r[j]);
}
void get(int no, int l, int r, int id) {
	int u = max(x[id] - 2LL *::r[id], (ll) - inf);
	int v = min(x[id] + 2LL *::r[id], (ll)inf);

	if (cmp[l] >= u and cmp[r] <= v) {
		u = max(y[id] - 2LL *::r[id], (ll) - inf);
		v = min(y[id] + 2LL *::r[id], (ll)inf);
		for (auto it = T[no].lower_bound(ii(u, -1)); it != T[no].end() and it->F <= v; it++) {
			int tid = it->S;
			if (par[tid] != -1) rem.emplace_back(y[tid], tid);
			else if (intersect(tid, id)) {
				par[tid] = id;
				rem.emplace_back(y[tid], tid);
			}
		}
		for (auto it : rem) {
			T[no].erase(it);
		}
		rem.clear();
		return;
	}

	if (cmp[r] < u or cmp[l] > v) return;
	int mid = (l + r) >> 1;
	get(2 * no, l, mid, id);
	get(2 * no + 1, mid + 1, r, id);

}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	x.resize(n), y.resize(n), r.resize(n);
	par = vi(n, -1);

	FOR (i, 0, n - 1) {
		cin >> x[i] >> y[i] >> r[i];
		cmp.emplace_back(x[i]);
	}
	sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());

	vi id(n); iota(all(id), 0);
	sort(all(id), [&](int x, int y) {
		if (r[x] == r[y]) return x < y;
		return r[x] > r[y];
	});

	FOR (i, 0, n - 1) ins(1, 0, sz(cmp) - 1, i);

	for (int i : id) if (par[i] == -1) {
			get(1, 0, sz(cmp) - 1, i);
		}

	FOR (i, 0, n - 1) cout << par[i] + 1 << " ";



	return 0;
}

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