oj.uz

Submission #852334

# Submission time Handle Problem Language Result Execution time Memory
852334 2023-09-21T15:48:43 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 239140 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 (R[cand] < R[t] || (R[cand] == R[t] && cand > 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 idx, int y, int r, int li) {
		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;
			if (XL[it->second] <= li) 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--;
			if (XL[it->second] <= li) break;
			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 y, int r, int li) {
		p += base; p--;
		while (p >= 1) {
			if (L[p] <= li) break;
			chk_node(p, y, r, li);
			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], 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:128:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  128 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:128:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  128 |  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 6492 KB Output is correct
12 Correct 1 ms 6492 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 Correct 2 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8192 KB Output is correct
20 Correct 5 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 9 ms 9564 KB Output is correct
24 Correct 5 ms 8652 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 120216 KB Output is correct
2 Correct 424 ms 121504 KB Output is correct
3 Correct 408 ms 120500 KB Output is correct
4 Correct 394 ms 120084 KB Output is correct
5 Correct 363 ms 67932 KB Output is correct
6 Correct 386 ms 130484 KB Output is correct
7 Correct 401 ms 122924 KB Output is correct
8 Correct 411 ms 125960 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 259 ms 57552 KB Output is correct
3 Correct 1038 ms 187028 KB Output is correct
4 Correct 978 ms 185444 KB Output is correct
5 Correct 1237 ms 183448 KB Output is correct
6 Correct 449 ms 86056 KB Output is correct
7 Correct 131 ms 44180 KB Output is correct
8 Correct 16 ms 14576 KB Output is correct
9 Correct 1136 ms 188432 KB Output is correct
10 Correct 1589 ms 178428 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 176752 KB Output is correct
2 Correct 316 ms 142148 KB Output is correct
3 Correct 688 ms 127924 KB Output is correct
4 Correct 360 ms 145892 KB Output is correct
5 Correct 339 ms 143660 KB Output is correct
6 Correct 613 ms 121208 KB Output is correct

Subtask #5
30.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 6492 KB Output is correct
12 Correct 1 ms 6492 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 Correct 2 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8192 KB Output is correct
20 Correct 5 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 9 ms 9564 KB Output is correct
24 Correct 5 ms 8652 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8796 KB Output is correct
27 Correct 8 ms 10072 KB Output is correct
28 Correct 9 ms 10076 KB Output is correct
29 Correct 8 ms 10076 KB Output is correct
30 Correct 13 ms 11868 KB Output is correct
31 Correct 10 ms 11096 KB Output is correct
32 Correct 10 ms 11096 KB Output is correct
33 Correct 99 ms 35168 KB Output is correct
34 Correct 106 ms 35012 KB Output is correct
35 Correct 109 ms 35016 KB Output is correct
36 Correct 152 ms 47812 KB Output is correct
37 Correct 146 ms 48324 KB Output is correct
38 Correct 168 ms 50488 KB Output is correct
39 Correct 113 ms 11564 KB Output is correct
40 Correct 114 ms 11608 KB Output is correct
41 Correct 110 ms 11620 KB Output is correct
42 Correct 120 ms 11768 KB Output is correct
43 Correct 102 ms 42268 KB Output is correct
44 Correct 96 ms 41252 KB Output is correct
45 Correct 106 ms 41924 KB Output is correct
46 Correct 95 ms 42176 KB Output is correct
47 Correct 93 ms 40904 KB Output is correct
48 Correct 101 ms 41924 KB Output is correct
49 Correct 91 ms 40752 KB Output is correct
50 Correct 93 ms 41548 KB Output is correct

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 6492 KB Output is correct
12 Correct 1 ms 6492 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 Correct 2 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8192 KB Output is correct
20 Correct 5 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 9 ms 9564 KB Output is correct
24 Correct 5 ms 8652 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8796 KB Output is correct
27 Correct 406 ms 120216 KB Output is correct
28 Correct 424 ms 121504 KB Output is correct
29 Correct 408 ms 120500 KB Output is correct
30 Correct 394 ms 120084 KB Output is correct
31 Correct 363 ms 67932 KB Output is correct
32 Correct 386 ms 130484 KB Output is correct
33 Correct 401 ms 122924 KB Output is correct
34 Correct 411 ms 125960 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 259 ms 57552 KB Output is correct
37 Correct 1038 ms 187028 KB Output is correct
38 Correct 978 ms 185444 KB Output is correct
39 Correct 1237 ms 183448 KB Output is correct
40 Correct 449 ms 86056 KB Output is correct
41 Correct 131 ms 44180 KB Output is correct
42 Correct 16 ms 14576 KB Output is correct
43 Correct 1136 ms 188432 KB Output is correct
44 Correct 1589 ms 178428 KB Output is correct
45 Correct 695 ms 176752 KB Output is correct
46 Correct 316 ms 142148 KB Output is correct
47 Correct 688 ms 127924 KB Output is correct
48 Correct 360 ms 145892 KB Output is correct
49 Correct 339 ms 143660 KB Output is correct
50 Correct 613 ms 121208 KB Output is correct
51 Correct 8 ms 10072 KB Output is correct
52 Correct 9 ms 10076 KB Output is correct
53 Correct 8 ms 10076 KB Output is correct
54 Correct 13 ms 11868 KB Output is correct
55 Correct 10 ms 11096 KB Output is correct
56 Correct 10 ms 11096 KB Output is correct
57 Correct 99 ms 35168 KB Output is correct
58 Correct 106 ms 35012 KB Output is correct
59 Correct 109 ms 35016 KB Output is correct
60 Correct 152 ms 47812 KB Output is correct
61 Correct 146 ms 48324 KB Output is correct
62 Correct 168 ms 50488 KB Output is correct
63 Correct 113 ms 11564 KB Output is correct
64 Correct 114 ms 11608 KB Output is correct
65 Correct 110 ms 11620 KB Output is correct
66 Correct 120 ms 11768 KB Output is correct
67 Correct 102 ms 42268 KB Output is correct
68 Correct 96 ms 41252 KB Output is correct
69 Correct 106 ms 41924 KB Output is correct
70 Correct 95 ms 42176 KB Output is correct
71 Correct 93 ms 40904 KB Output is correct
72 Correct 101 ms 41924 KB Output is correct
73 Correct 91 ms 40752 KB Output is correct
74 Correct 93 ms 41548 KB Output is correct
75 Correct 408 ms 119596 KB Output is correct
76 Correct 409 ms 120484 KB Output is correct
77 Correct 379 ms 119792 KB Output is correct
78 Correct 405 ms 120236 KB Output is correct
79 Correct 492 ms 120780 KB Output is correct
80 Correct 410 ms 119480 KB Output is correct
81 Correct 897 ms 181300 KB Output is correct
82 Correct 759 ms 171444 KB Output is correct
83 Correct 755 ms 172256 KB Output is correct
84 Correct 1234 ms 196948 KB Output is correct
85 Correct 819 ms 177628 KB Output is correct
86 Correct 734 ms 170420 KB Output is correct
87 Correct 2645 ms 239140 KB Output is correct
88 Correct 405 ms 22992 KB Output is correct
89 Correct 401 ms 23476 KB Output is correct
90 Correct 401 ms 23308 KB Output is correct
91 Correct 431 ms 22968 KB Output is correct
92 Correct 385 ms 22184 KB Output is correct
93 Correct 379 ms 142284 KB Output is correct
94 Correct 2920 ms 90924 KB Output is correct
95 Correct 365 ms 142516 KB Output is correct
96 Correct 370 ms 141920 KB Output is correct
97 Correct 2236 ms 67316 KB Output is correct
98 Correct 435 ms 134244 KB Output is correct
99 Correct 382 ms 141236 KB Output is correct
100 Correct 328 ms 141284 KB Output is correct
101 Correct 554 ms 144912 KB Output is correct
102 Correct 382 ms 141236 KB Output is correct
103 Execution timed out 3019 ms 85516 KB Time limit exceeded
104 Halted 0 ms 0 KB -