Submission #851452

#	Time	Username	Problem	Language	Result	Execution time	Memory
851452		dlalswp25	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3022 ms	230664 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int INF = 1010101010;
const int K = 2;

int N;
int X[303030];
int Y[303030];
int R[303030];
int XL[303030];
int XR[303030];
int ans[303030];
int cur;
char rr;

void rf(int &x) {
	x = 0;
	int sgn = 0;
	while (rr < 48 && rr != '-') rr = getchar();
	if (rr == '-') { sgn = 1; rr = getchar(); }
	while (47 < rr) { x = (x << 3) + (x << 1) + (rr & 15); rr = getchar(); }
	if (sgn) x = -x;
}

inline bool intersect(int i, int j) {
	long long dx = X[i] - X[j], dy = Y[i] - Y[j], r = R[i] + R[j];
	return dx * dx + dy * dy <= r * r;
}

inline void chk(int cand) {
	int &t = ans[cur];
	if (pii(R[cand], -cand) < pii(R[t], -t)) return;
	if (intersect(cur, cand)) t = cand;
}

struct SegTree {
	struct Node {
		set<pii> s;
	};

	int n, base;
	vector<Node> T;

	SegTree(int _n) : n(_n) {
		for (base = 1; base < n; base <<= 1);
		T.resize(base + base);
	}

	void upd(int p, int q, pii x) {
		p += base; q += base;
		p--; q--;
		while (p <= q) {
			if (p & 1) T[p++].s.insert(x);
			if (~q & 1) T[q--].s.insert(x);
			p >>= 1; q >>= 1;
		}
	}

	void get(int p, int y, int r) {
		p += base; p--;
		vector<pair<int, set<pii>::iterator>> v;
		while (p >= 1) {
			v.emplace_back(p, T[p].s.lower_bound({y, 0}));
			p >>= 1;
		}
		pii m1, m2;
		m1 = m2 = {INF, 0};
		for (auto j : v) {
			int p = j.first;
			auto it = j.second;
			if (it == T[p].s.end()) continue;
			if (*it <= m1) {
				m2 = m1; m1 = *it;
				if (m1.first <= (long long)y + r + r && next(it) != T[p].s.end()) m2 = min(m2, *next(it));
			} else if (m1.first <= (long long)y + r + r) {
				m2 = min(m2, *it);
			}
		}
		if (m1.first != INF) chk(m1.second);
		if (m2.first != INF) chk(m2.second);
		m1 = m2 = {-INF, 0};
		for (auto j : v) {
			int p = j.first;
			auto it = j.second;
			if (it == T[p].s.begin()) continue;
			auto pit = prev(it);
			if (*pit >= m1) {
				m2 = m1; m1 = *pit;
				if (m1.first >= (long long)y - r - r && pit != T[p].s.begin()) m2 = max(m2, *prev(pit));
			} else if (m1.first >= (long long)y - r - r) {
				m2 = max(m2, *pit);
			}
		}
		if (m1.first != -INF) chk(m1.second);
		if (m2.first != -INF) chk(m2.second);
	}
};

int main() {
	rf(N);
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		rf(X[i]); rf(Y[i]); rf(R[i]);
		XL[i] = X[i] - R[i], XR[i] = X[i] + R[i];
		v.push_back(XL[i]);
		v.push_back(XR[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for (int i = 1; i <= N; i++) {
		XL[i] = lower_bound(v.begin(), v.end(), XL[i]) - v.begin() + 1;
		XR[i] = lower_bound(v.begin(), v.end(), XR[i]) - v.begin() + 1;
	}

	int M = v.size();
	SegTree seg(M);

	vector<int> idx(N);
	iota(idx.begin(), idx.end(), 1);
	sort(idx.begin(), idx.end(), [&](int a, int b) {
		return pii(R[a], -a) > pii(R[b], -b);
	});

	for (int i : idx) {
		cur = i;
		ans[i] = i;
		seg.get(XL[i], Y[i], R[i]);
		seg.get(XR[i], Y[i], R[i]);
		if (ans[i] == i) seg.upd(XL[i], XR[i], {Y[i], i});
	}

	for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:135:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  135 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:135:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  135 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~

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