oj.uz

Submission #855970

# Submission time Handle Problem Language Result Execution time Memory
855970 2023-10-02T13:01:45 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 400500 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

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

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 bool chk(int cand) {
	if (intersect(cur, cand)) { ans[cand] = cur; return true; }
	return false;
}

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 chk_node(int idx, int y) {
		auto it = T[idx].s.lower_bound({y, 0});
		auto tmp = it;
		int cnt = 0;
		while (it != T[idx].s.begin()) {
			it--;
			if (ans[it->second] || ::chk(it->second)) { it = T[idx].s.erase(it); continue; }
			cnt++;
			if (cnt >= 2) break;
		}
		cnt = 0;
		it = tmp;
		while (it != T[idx].s.end()) {
			if (ans[it->second] || ::chk(it->second)) { it = T[idx].s.erase(it); continue; }
			cnt++;
			if (cnt >= 2) break;
			it++;
		}
	}

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

	void chk(int p, int q, int y) {
		p += base; q += base;
		p--; q--;
		while (p <= q) {
			if (p & 1) chk_node(p++, y);
			if (~q & 1) chk_node(q--, y);
			p >>= 1; q >>= 1;
		}
	}
};

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

	for (int i = 1; i <= N; i++) {
		seg.upd(XL[i], {Y[i], i});
		seg.upd(XR[i], {Y[i], i});
	}

	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) {
		if (ans[i]) continue;
		cur = ans[i] = i;
		seg.chk(XL[i], XR[i], Y[i]);
	}

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

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 4 ms 7772 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 400500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1815 ms 153360 KB Output is correct
3 Execution timed out 3046 ms 353144 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 357396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 4 ms 7772 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6504 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 4 ms 7772 KB Output isn't correct
17 Halted 0 ms 0 KB -