oj.uz

Submission #851534

# Submission time Handle Problem Language Result Execution time Memory
851534 2023-09-20T04:50:10 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
19 / 100
 689 ms 178256 KB 
#include <bits/stdc++.h>

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

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;
	vector<int> L;

	SegTree(int _n) : n(_n) {
		for (base = 1; base < n; base <<= 1);
		T.resize(base + base);
		L.resize(base + base);
		for (int i = base; i < base + base; i++) L[i] = i - base + 1;
		for (int i = base - 1; i >= 1; i--) L[i] = L[i << 1];
	}

	void chk_node(int idxl, int idxr, int y, int r) {
		auto itl = T[idxl].s.lower_bound({y, 0});
		auto itr = T[idxr].s.lower_bound({y, 0});
		auto tmpl = itl, tmpr = itr;
		if (idxl == idxr) {
			for (int i = 0; i < 3; i++) {
				if (itl == T[idxl].s.end()) break;
				chk(itl->second);
				// if (itl->first >= (long long)y + r + r) break;
				if (i < K - 1) itl++;
			}
		} else {
			for (int i = 0; i < 3; i++) {
				bool fl = (itl == T[idxl].s.end());
				bool fr = (itr == T[idxr].s.end());
				if (fl && fr) break;
				if (fr || (!fl && itl->first < itr->first)) {
					chk(itl->second);
					if (i < 2) itl++;
				} else {
					chk(itr->second);
					if (i < 2) itr++;
				}
			}
		}
		itl = tmpl; itr = tmpr;
		if (idxl == idxr) {
			for (int i = 0; i < 3; i++) {
				if (itl == T[idxl].s.begin()) break;
				itl--;
				chk(itl->second);
				// if (itl->first <= (long long)y - r - r) break;
			}
		} else {
			for (int i = 0; i < 3; i++) {
				bool fl = (itl == T[idxl].s.begin());
				bool fr = (itr == T[idxr].s.begin());
				if (fl && fr) break;
				if (fr || (!fl && prev(itl)->first < prev(itr)->first)) {
					itl--;
					chk(itl->second);
				} else {
					itr--;
					chk(itr->second);
				}
			}
		}

		// auto it = T[idx].s.lower_bound({y, 0});
		// auto tmp = it;
		// for (int i = 0; i < K; i++) {
		// 	if (it == T[idx].s.end()) break;
		// 	chk(it->second);
		// 	if (it->first >= (long long)y + r + r) break;
		// 	if (i < K - 1) it++;
		// }
		// it = tmp;
		// for (int i = 0; i < K; i++) {
		// 	if (it == T[idx].s.begin()) break;
		// 	it--;
		// 	chk(it->second);
		// 	if (it->first <= (long long)y - r - r) break;
		// }
	}

	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 q, int y, int r) {
		p += base; q += base;
		p--; q--;
		while (p > 1) {
			chk_node(p, q, y, r);
			p >>= 1; q >>= 1;
		}
	}

	// void get(int p, int y, int r, int li) {
	// 	p += base; p--;
	// 	while (p >= 1) {
	// 		if (L[p] <= li) break;
	// 		chk_node(p, y, r);
	// 		p >>= 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);

	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], XR[i], Y[i], R[i]);
		// seg.get(XL[i], Y[i], R[i], 0);
		// seg.get(XR[i], Y[i], R[i], XL[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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 6492 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 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6636 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6604 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8796 KB Output is correct
23 Correct 10 ms 9456 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 119824 KB Output is correct
2 Correct 349 ms 121104 KB Output is correct
3 Correct 336 ms 120228 KB Output is correct
4 Correct 332 ms 120248 KB Output is correct
5 Correct 312 ms 68836 KB Output is correct
6 Correct 352 ms 132024 KB Output is correct
7 Correct 362 ms 122552 KB Output is correct
8 Correct 348 ms 125624 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 275 ms 57372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 689 ms 178256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 6492 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 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6636 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6604 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8796 KB Output is correct
23 Correct 10 ms 9456 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct
27 Correct 8 ms 10076 KB Output is correct
28 Correct 8 ms 10144 KB Output is correct
29 Correct 8 ms 10076 KB Output is correct
30 Correct 15 ms 11868 KB Output is correct
31 Correct 11 ms 11172 KB Output is correct
32 Correct 9 ms 10952 KB Output is correct
33 Correct 95 ms 35012 KB Output is correct
34 Correct 98 ms 35244 KB Output is correct
35 Correct 102 ms 35148 KB Output is correct
36 Correct 139 ms 47816 KB Output is correct
37 Correct 152 ms 48272 KB Output is correct
38 Correct 160 ms 50528 KB Output is correct
39 Incorrect 145 ms 12224 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 6492 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 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6636 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6604 KB Output is correct
19 Correct 4 ms 8284 KB Output is correct
20 Correct 4 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8796 KB Output is correct
23 Correct 10 ms 9456 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct
27 Correct 342 ms 119824 KB Output is correct
28 Correct 349 ms 121104 KB Output is correct
29 Correct 336 ms 120228 KB Output is correct
30 Correct 332 ms 120248 KB Output is correct
31 Correct 312 ms 68836 KB Output is correct
32 Correct 352 ms 132024 KB Output is correct
33 Correct 362 ms 122552 KB Output is correct
34 Correct 348 ms 125624 KB Output is correct
35 Correct 1 ms 6488 KB Output is correct
36 Incorrect 275 ms 57372 KB Output isn't correct
37 Halted 0 ms 0 KB -