Submission #794621

#	Time	Username	Problem	Language	Result	Execution time	Memory
794621		dlalswp25	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3082 ms	410628 KiB

circle_selection

#include <bits/stdc++.h>

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

const int INF = 2020202020;

int N;
int X[303030];
int Y[303030];
int R[303030];
int C[303030][4];
int ans[303030];
int Q[8][2][3] = {
	{{1, 3, 0}, {1, 0, 0}},
	{{0, 3, 1}, {1, 1, 0}},
	{{0, 2, 1}, {0, 1, 0}},
	{{1, 2, 0}, {1, 0, 1}},
	{{1, 3, 0}, {0, 1, 1}},
	{{0, 3, 1}, {0, 0, 1}},
	{{0, 2, 1}, {1, 0, 1}},
	{{1, 2, 0}, {0, 1, 0}}
};

struct BIT {
	struct Node {
		set<piii> S;

		void add(piii x) {
			auto it = S.insert(x).first;
			if (it != S.begin() && std::get<1>(*prev(it)) <= std::get<1>(*it)) {
				S.erase(it); return;
			}
			while (next(it) != S.end() && std::get<1>(*next(it)) >= std::get<1>(*it)) {
				S.erase(next(it));
			}
		}

		pii get(int y) {
			auto it = S.lower_bound(piii(y + 1, -INF, 0));
			if (it == S.begin()) return {INF, 0};
			int _, z, i; tie(_, z, i) = *prev(it);
			return {z, i};
		}
	};

	int n;
	vector<Node> T;

	BIT(int _n) : n(_n), T(_n + 1) {}

	void upd(int x, int y, int z, int i) {
		piii t(y, z, i);
		for (int i = x; i <= n; i += i&-i) T[i].add(t);
	}

	int query(int x, int y) {
		pii ret = {INF, 0};
		for (int i = x; i; i -= i&-i) ret = min(ret, T[i].get(y));
		return ret.second;
	}
};

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

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d", &X[i], &Y[i], &R[i]);
		C[i][0] = X[i];
		C[i][1] = Y[i];
		C[i][2] = X[i] + Y[i];
		C[i][3] = Y[i] - X[i];
	}
	for (int i = 0; i < 4; i++) {
		vector<int> v;
		for (int j = 1; j <= N; j++) v.push_back(C[j][i]);
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		for (int j = 1; j <= N; j++) {
			C[j][i] = lower_bound(v.begin(), v.end(), C[j][i]) - v.begin() + 1;
		}
	}

	BIT seg[8] {
		{N}, {N}, {N}, {N}, {N}, {N}, {N}, {N}
	};

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

	for (int i : V) {
		ans[i] = i;
		int x[8][3];
		for (int j = 0; j < 8; j++) {
			for (int k = 0; k < 3; k++) {
				x[j][k] = C[i][Q[j][0][k]];
				if (Q[j][1][k]) x[j][k] = N - x[j][k] + 1;
			}
		}
		for (int j = 0; j < 8; j++) {
			int t = seg[j].query(x[j][0], x[j][1]);
			if (!t || !intersect(i, t)) continue;
			if (pii(R[t], -t) > pii(R[ans[i]], -ans[i])) ans[i] = t;
		}
		if (ans[i] == i) {
			for (int j = 0; j < 8; j++) {
				seg[j].upd(x[j][0], x[j][1], x[j][2], 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:120:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  120 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:120:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~
circle_selection.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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