Submission #794677

#	Time	Username	Problem	Language	Result	Execution time	Memory
794677		dlalswp25	Circle selection (APIO18_circle_selection)	C++14	72 / 100	3053 ms	202684 KiB

circle_selection

#include <bits/stdc++.h>

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

const int K = 12;

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

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;
}

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

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

	int n;
	vector<Node> T;

	SegTree(int _n) : n(_n), T(4 * _n) {}

	void chk_node(int idx, int y) {
		auto it = T[idx].s.lower_bound({y, 0});
		for (int i = 0; i < K; i++) {
			if (it == T[idx].s.end()) break;
			chk(it->second);
			it++;
		}
	}

	void upd(int idx, int s, int e, int p, int q, pii &x) {
		if (q < p || q < s || e < p) return;
		if (p <= s && e <= q) {
			T[idx].s.insert(x);
			return;
		}
		int m = s + e >> 1;
		upd(idx << 1, s, m, p, q, x);
		upd(idx << 1 | 1, m + 1, e, p, q, x);
	}

	void upd(int p, int q, pii x) { upd(1, 1, n, p, q, x); }

	void get(int idx, int s, int e, int p, int y) {
		if (p < s || e < p) return;
		chk_node(idx, y);
		if (s == e) return;
		int m = s + e >> 1;
		get(idx << 1, s, m, p, y);
		get(idx << 1 | 1, m + 1, e, p, y);
	}

	void get(int p, int y) { get(1, 1, n, p, y); }
};

int main() {
	scanf("%d", &N);
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d", &X[i], &Y[i], &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(XL[i], Y[i] + R[i]);
		seg.get(XR[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] + R[i], i});
	}

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

Compilation message (stderr)

circle_selection.cpp: In member function 'void SegTree::upd(int, int, int, int, int, pii&)':
circle_selection.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int m = s + e >> 1;
      |           ~~^~~
circle_selection.cpp: In member function 'void SegTree::get(int, int, int, int, int)':
circle_selection.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int m = s + e >> 1;
      |           ~~^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:108:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:108:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~
circle_selection.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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