oj.uz

Submission #855635

# Submission time Handle Problem Language Result Execution time Memory
855635 2023-10-01T15:02:17 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 247284 KB 
#pragma GCC optimize("O3")
#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 Node {
	set<pii> s;
} T[2121212];

int L[2121212];

struct SegTree {
	int n, base;

	void init(int _n) {
		n = _n;
		for (base = 1; base < n; base <<= 1);
		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;
		}
	}
} seg;

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();
	seg.init(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 22 ms 107100 KB Output is correct
2 Correct 22 ms 107096 KB Output is correct
3 Correct 22 ms 107100 KB Output is correct
4 Correct 22 ms 107100 KB Output is correct
5 Correct 22 ms 107012 KB Output is correct
6 Correct 22 ms 107100 KB Output is correct
7 Correct 22 ms 107100 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 21 ms 107100 KB Output is correct
11 Correct 22 ms 107096 KB Output is correct
12 Correct 22 ms 107100 KB Output is correct
13 Correct 22 ms 107128 KB Output is correct
14 Correct 22 ms 107004 KB Output is correct
15 Correct 22 ms 107096 KB Output is correct
16 Correct 22 ms 107096 KB Output is correct
17 Correct 23 ms 107200 KB Output is correct
18 Correct 23 ms 107100 KB Output is correct
19 Correct 26 ms 107548 KB Output is correct
20 Correct 25 ms 107356 KB Output is correct
21 Correct 25 ms 107356 KB Output is correct
22 Correct 26 ms 107868 KB Output is correct
23 Correct 30 ms 108624 KB Output is correct
24 Correct 26 ms 107868 KB Output is correct
25 Correct 25 ms 107592 KB Output is correct
26 Correct 28 ms 107868 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 126320 KB Output is correct
2 Correct 364 ms 126276 KB Output is correct
3 Correct 382 ms 124464 KB Output is correct
4 Correct 356 ms 125500 KB Output is correct
5 Correct 302 ms 122356 KB Output is correct
6 Correct 369 ms 134800 KB Output is correct
7 Correct 346 ms 127300 KB Output is correct
8 Correct 347 ms 129208 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 107100 KB Output is correct
2 Correct 285 ms 135356 KB Output is correct
3 Correct 955 ms 191488 KB Output is correct
4 Correct 944 ms 190840 KB Output is correct
5 Correct 1202 ms 189924 KB Output is correct
6 Correct 421 ms 140076 KB Output is correct
7 Correct 149 ms 121796 KB Output is correct
8 Correct 37 ms 111052 KB Output is correct
9 Correct 1073 ms 194424 KB Output is correct
10 Correct 1566 ms 184400 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 182524 KB Output is correct
2 Correct 310 ms 146776 KB Output is correct
3 Correct 680 ms 132372 KB Output is correct
4 Correct 363 ms 150664 KB Output is correct
5 Correct 332 ms 147892 KB Output is correct
6 Correct 576 ms 127688 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 107100 KB Output is correct
2 Correct 22 ms 107096 KB Output is correct
3 Correct 22 ms 107100 KB Output is correct
4 Correct 22 ms 107100 KB Output is correct
5 Correct 22 ms 107012 KB Output is correct
6 Correct 22 ms 107100 KB Output is correct
7 Correct 22 ms 107100 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 21 ms 107100 KB Output is correct
11 Correct 22 ms 107096 KB Output is correct
12 Correct 22 ms 107100 KB Output is correct
13 Correct 22 ms 107128 KB Output is correct
14 Correct 22 ms 107004 KB Output is correct
15 Correct 22 ms 107096 KB Output is correct
16 Correct 22 ms 107096 KB Output is correct
17 Correct 23 ms 107200 KB Output is correct
18 Correct 23 ms 107100 KB Output is correct
19 Correct 26 ms 107548 KB Output is correct
20 Correct 25 ms 107356 KB Output is correct
21 Correct 25 ms 107356 KB Output is correct
22 Correct 26 ms 107868 KB Output is correct
23 Correct 30 ms 108624 KB Output is correct
24 Correct 26 ms 107868 KB Output is correct
25 Correct 25 ms 107592 KB Output is correct
26 Correct 28 ms 107868 KB Output is correct
27 Correct 29 ms 109912 KB Output is correct
28 Correct 30 ms 109916 KB Output is correct
29 Correct 32 ms 110080 KB Output is correct
30 Correct 34 ms 111440 KB Output is correct
31 Correct 31 ms 110876 KB Output is correct
32 Correct 31 ms 110840 KB Output is correct
33 Correct 107 ms 113352 KB Output is correct
34 Correct 117 ms 113264 KB Output is correct
35 Correct 121 ms 113532 KB Output is correct
36 Correct 171 ms 125580 KB Output is correct
37 Correct 163 ms 126140 KB Output is correct
38 Correct 193 ms 128628 KB Output is correct
39 Correct 135 ms 113060 KB Output is correct
40 Correct 130 ms 113096 KB Output is correct
41 Correct 132 ms 113096 KB Output is correct
42 Correct 139 ms 113344 KB Output is correct
43 Correct 109 ms 119996 KB Output is correct
44 Correct 107 ms 119228 KB Output is correct
45 Correct 112 ms 120032 KB Output is correct
46 Correct 108 ms 119748 KB Output is correct
47 Correct 106 ms 118948 KB Output is correct
48 Correct 108 ms 119748 KB Output is correct
49 Correct 112 ms 118596 KB Output is correct
50 Correct 106 ms 119420 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 107100 KB Output is correct
2 Correct 22 ms 107096 KB Output is correct
3 Correct 22 ms 107100 KB Output is correct
4 Correct 22 ms 107100 KB Output is correct
5 Correct 22 ms 107012 KB Output is correct
6 Correct 22 ms 107100 KB Output is correct
7 Correct 22 ms 107100 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 21 ms 107100 KB Output is correct
11 Correct 22 ms 107096 KB Output is correct
12 Correct 22 ms 107100 KB Output is correct
13 Correct 22 ms 107128 KB Output is correct
14 Correct 22 ms 107004 KB Output is correct
15 Correct 22 ms 107096 KB Output is correct
16 Correct 22 ms 107096 KB Output is correct
17 Correct 23 ms 107200 KB Output is correct
18 Correct 23 ms 107100 KB Output is correct
19 Correct 26 ms 107548 KB Output is correct
20 Correct 25 ms 107356 KB Output is correct
21 Correct 25 ms 107356 KB Output is correct
22 Correct 26 ms 107868 KB Output is correct
23 Correct 30 ms 108624 KB Output is correct
24 Correct 26 ms 107868 KB Output is correct
25 Correct 25 ms 107592 KB Output is correct
26 Correct 28 ms 107868 KB Output is correct
27 Correct 363 ms 126320 KB Output is correct
28 Correct 364 ms 126276 KB Output is correct
29 Correct 382 ms 124464 KB Output is correct
30 Correct 356 ms 125500 KB Output is correct
31 Correct 302 ms 122356 KB Output is correct
32 Correct 369 ms 134800 KB Output is correct
33 Correct 346 ms 127300 KB Output is correct
34 Correct 347 ms 129208 KB Output is correct
35 Correct 22 ms 107100 KB Output is correct
36 Correct 285 ms 135356 KB Output is correct
37 Correct 955 ms 191488 KB Output is correct
38 Correct 944 ms 190840 KB Output is correct
39 Correct 1202 ms 189924 KB Output is correct
40 Correct 421 ms 140076 KB Output is correct
41 Correct 149 ms 121796 KB Output is correct
42 Correct 37 ms 111052 KB Output is correct
43 Correct 1073 ms 194424 KB Output is correct
44 Correct 1566 ms 184400 KB Output is correct
45 Correct 690 ms 182524 KB Output is correct
46 Correct 310 ms 146776 KB Output is correct
47 Correct 680 ms 132372 KB Output is correct
48 Correct 363 ms 150664 KB Output is correct
49 Correct 332 ms 147892 KB Output is correct
50 Correct 576 ms 127688 KB Output is correct
51 Correct 29 ms 109912 KB Output is correct
52 Correct 30 ms 109916 KB Output is correct
53 Correct 32 ms 110080 KB Output is correct
54 Correct 34 ms 111440 KB Output is correct
55 Correct 31 ms 110876 KB Output is correct
56 Correct 31 ms 110840 KB Output is correct
57 Correct 107 ms 113352 KB Output is correct
58 Correct 117 ms 113264 KB Output is correct
59 Correct 121 ms 113532 KB Output is correct
60 Correct 171 ms 125580 KB Output is correct
61 Correct 163 ms 126140 KB Output is correct
62 Correct 193 ms 128628 KB Output is correct
63 Correct 135 ms 113060 KB Output is correct
64 Correct 130 ms 113096 KB Output is correct
65 Correct 132 ms 113096 KB Output is correct
66 Correct 139 ms 113344 KB Output is correct
67 Correct 109 ms 119996 KB Output is correct
68 Correct 107 ms 119228 KB Output is correct
69 Correct 112 ms 120032 KB Output is correct
70 Correct 108 ms 119748 KB Output is correct
71 Correct 106 ms 118948 KB Output is correct
72 Correct 108 ms 119748 KB Output is correct
73 Correct 112 ms 118596 KB Output is correct
74 Correct 106 ms 119420 KB Output is correct
75 Correct 388 ms 130184 KB Output is correct
76 Correct 366 ms 128948 KB Output is correct
77 Correct 344 ms 129720 KB Output is correct
78 Correct 352 ms 130092 KB Output is correct
79 Correct 445 ms 130956 KB Output is correct
80 Correct 361 ms 130236 KB Output is correct
81 Correct 833 ms 189888 KB Output is correct
82 Correct 712 ms 181176 KB Output is correct
83 Correct 718 ms 180664 KB Output is correct
84 Correct 1184 ms 205332 KB Output is correct
85 Correct 811 ms 186540 KB Output is correct
86 Correct 706 ms 177888 KB Output is correct
87 Correct 2643 ms 247284 KB Output is correct
88 Correct 429 ms 127280 KB Output is correct
89 Correct 422 ms 126796 KB Output is correct
90 Correct 427 ms 128640 KB Output is correct
91 Correct 437 ms 128180 KB Output is correct
92 Correct 421 ms 128080 KB Output is correct
93 Correct 349 ms 149680 KB Output is correct
94 Correct 2807 ms 199796 KB Output is correct
95 Correct 346 ms 149272 KB Output is correct
96 Correct 362 ms 149596 KB Output is correct
97 Correct 2092 ms 174260 KB Output is correct
98 Correct 404 ms 142640 KB Output is correct
99 Correct 346 ms 149944 KB Output is correct
100 Correct 332 ms 150924 KB Output is correct
101 Correct 506 ms 154216 KB Output is correct
102 Correct 354 ms 149732 KB Output is correct
103 Execution timed out 3032 ms 193964 KB Time limit exceeded
104 Halted 0 ms 0 KB -