Submission #1235625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235625		Matthewwww	Circle selection (APIO18_circle_selection)	C++17	12 / 100	974 ms	698200 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define freopen(...) "i miss you"
#define err cerr
#else
#define err if (0) cerr
#endif

struct Sgt {
	int tl, tr, val = -1;
	Sgt *lft = nullptr, *rht = nullptr;
	Sgt (int l, int r): tl(l), tr(r) {}
	void push() {
		if (!lft) {
			int tm = tl+tr>>1;
			lft = new Sgt(tl, tm);
			rht = new Sgt(tm, tr);
		}
	}
	void update (int l, int r, int v) {
		if (l >= tr || tl >= r) return;
		if (l <= tl && r >= tr) {
			val = v;
			return;
		}
		push();
		lft->update(l, r, v);
		rht->update(l, r, v);
	}
	int query (int i) {
		if (tl == tr-1) return val;
		push();
		return max(val, (i < lft->tr ? lft : rht)->query(i));
	}
};

int d2 (pair<int, int> a, pair<int, int> b) {
	return (a.f-b.f)*(a.f-b.f)+(a.s-b.s)*(a.s-b.s);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<pair<pair<int, int>, int>> vt(n);
	for (auto &i: vt) cin >> i.f.f >> i.f.s >> i.s;
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int a, int b) { if (vt[a].s-vt[b].s) return vt[a].s > vt[b].s; return a < b;});
	vector<int> ans(n, -1);
	Sgt sgt(-2e9, 2e9+9);
	for (int i: ord) {
		int a = sgt.query(vt[i].f.f-vt[i].s), b = sgt.query(vt[i].f.f+vt[i].s);
		if (a > b) swap(a, b);
		if (!~a) {
			if (~b) ans[i] = b;
			else {
				sgt.update(vt[i].f.f-vt[i].s, vt[i].f.f+vt[i].s+1, i);
				ans[i] = i;
			}
		} else if (vt[a].s >= vt[b].s) ans[i] = a;
		else ans[i] = b;
	}
	for (int i: ans) cout << i+1 << " ";
}

// no llama :(

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