제출 #1235661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235661		Matthewwww	원 고르기 (APIO18_circle_selection)	C++17	15 / 100	527 ms	42164 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);
	set<pair<int, int>> st;
	priority_queue<pair<int, int>> pq;
	for (int i = 0; i < n; i++) {
		pq.push({vt[i].f.s+vt[i].s, i});
		pq.push({vt[i].f.s-vt[i].s, -i-1});
	}
	while (pq.size()) {
		int a = pq.top().s;
		pq.pop();
		if (a < 0) {
			a = -a-1;
			st.erase({vt[a].f.f, a});
			auto it = st.lower_bound({vt[a].f.f, a});
			if (it != st.end()) {
				a = (*it).s;
				auto l = st.find({vt[a].f.f, a});
				if (l != st.begin()) {
					--l;
					int b = (*l).s;
					++l;
					if (d2(vt[a].f, vt[b].f) <= (vt[a].s+vt[b].s)*(vt[a].s+vt[b].s)) {
						if (vt[a].s == vt[b].s) ans[max(a, b)] = min(a, b);
						else if (vt[a].s < vt[b].s) ans[a] = b;
						else ans[b] = a;
					}
				}
			}
		} else {
			st.insert({vt[a].f.f, a});
			auto l = st.find({vt[a].f.f, a});
			if (l != st.begin()) {
				--l;
				int b = (*l).s;
				++l;
				if (d2(vt[a].f, vt[b].f) <= (vt[a].s+vt[b].s)*(vt[a].s+vt[b].s)) {
					if (vt[a].s == vt[b].s) ans[max(a, b)] = min(a, b);
					else if (vt[a].s < vt[b].s) ans[a] = b;
					else ans[b] = a;
				}
			}
			if (++l != st.end()) {
				int b = (*l).s;
				if (d2(vt[a].f, vt[b].f) <= (vt[a].s+vt[b].s)*(vt[a].s+vt[b].s)) {
					if (vt[a].s == vt[b].s) ans[max(a, b)] = min(a, b);
					else if (vt[a].s < vt[b].s) ans[a] = b;
					else ans[b] = a;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) cout << (~ans[i] ? ans[i] : i)+1 << " ";
	cout << "\n";
}

// no llama :(

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