oj.uz

Submission #855637

# Submission time Handle Problem Language Result Execution time Memory
855637 2023-10-01T15:07:23 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 240992 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;
}

set<pii> 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].lower_bound({y, 0});
		auto tmp = it;
		for (int i = 0; i < K; i++) {
			if (it == T[idx].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].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++].insert(x);
			if (~q & 1) T[q--].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:126:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  126 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:126:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |  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 21 ms 107096 KB Output is correct
3 Correct 21 ms 107100 KB Output is correct
4 Correct 21 ms 107028 KB Output is correct
5 Correct 22 ms 107100 KB Output is correct
6 Correct 21 ms 107100 KB Output is correct
7 Correct 22 ms 106944 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 22 ms 107100 KB Output is correct
11 Correct 22 ms 106980 KB Output is correct
12 Correct 22 ms 107096 KB Output is correct
13 Correct 22 ms 107100 KB Output is correct
14 Correct 21 ms 107100 KB Output is correct
15 Correct 22 ms 107008 KB Output is correct
16 Correct 23 ms 107096 KB Output is correct
17 Correct 22 ms 107096 KB Output is correct
18 Correct 22 ms 107100 KB Output is correct
19 Correct 25 ms 107356 KB Output is correct
20 Correct 25 ms 107320 KB Output is correct
21 Correct 25 ms 107424 KB Output is correct
22 Correct 26 ms 107824 KB Output is correct
23 Correct 30 ms 108392 KB Output is correct
24 Correct 26 ms 107612 KB Output is correct
25 Correct 25 ms 107580 KB Output is correct
26 Correct 25 ms 107776 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 121528 KB Output is correct
2 Correct 398 ms 121672 KB Output is correct
3 Correct 354 ms 120800 KB Output is correct
4 Correct 356 ms 122448 KB Output is correct
5 Correct 314 ms 121272 KB Output is correct
6 Correct 357 ms 131764 KB Output is correct
7 Correct 356 ms 124792 KB Output is correct
8 Correct 353 ms 127140 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 107064 KB Output is correct
2 Correct 274 ms 133756 KB Output is correct
3 Correct 936 ms 188172 KB Output is correct
4 Correct 967 ms 186212 KB Output is correct
5 Correct 1177 ms 185220 KB Output is correct
6 Correct 394 ms 137920 KB Output is correct
7 Correct 149 ms 120488 KB Output is correct
8 Correct 37 ms 110796 KB Output is correct
9 Correct 1024 ms 189640 KB Output is correct
10 Correct 1585 ms 180092 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 178612 KB Output is correct
2 Correct 302 ms 142572 KB Output is correct
3 Correct 717 ms 128636 KB Output is correct
4 Correct 346 ms 146788 KB Output is correct
5 Correct 328 ms 144496 KB Output is correct
6 Correct 568 ms 123060 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 21 ms 107096 KB Output is correct
3 Correct 21 ms 107100 KB Output is correct
4 Correct 21 ms 107028 KB Output is correct
5 Correct 22 ms 107100 KB Output is correct
6 Correct 21 ms 107100 KB Output is correct
7 Correct 22 ms 106944 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 22 ms 107100 KB Output is correct
11 Correct 22 ms 106980 KB Output is correct
12 Correct 22 ms 107096 KB Output is correct
13 Correct 22 ms 107100 KB Output is correct
14 Correct 21 ms 107100 KB Output is correct
15 Correct 22 ms 107008 KB Output is correct
16 Correct 23 ms 107096 KB Output is correct
17 Correct 22 ms 107096 KB Output is correct
18 Correct 22 ms 107100 KB Output is correct
19 Correct 25 ms 107356 KB Output is correct
20 Correct 25 ms 107320 KB Output is correct
21 Correct 25 ms 107424 KB Output is correct
22 Correct 26 ms 107824 KB Output is correct
23 Correct 30 ms 108392 KB Output is correct
24 Correct 26 ms 107612 KB Output is correct
25 Correct 25 ms 107580 KB Output is correct
26 Correct 25 ms 107776 KB Output is correct
27 Correct 30 ms 109660 KB Output is correct
28 Correct 31 ms 109568 KB Output is correct
29 Correct 32 ms 109392 KB Output is correct
30 Correct 34 ms 111188 KB Output is correct
31 Correct 31 ms 110548 KB Output is correct
32 Correct 30 ms 110424 KB Output is correct
33 Correct 131 ms 111508 KB Output is correct
34 Correct 111 ms 111472 KB Output is correct
35 Correct 120 ms 111560 KB Output is correct
36 Correct 168 ms 124100 KB Output is correct
37 Correct 181 ms 124524 KB Output is correct
38 Correct 176 ms 126740 KB Output is correct
39 Correct 143 ms 112324 KB Output is correct
40 Correct 137 ms 112116 KB Output is correct
41 Correct 134 ms 112160 KB Output is correct
42 Correct 139 ms 112576 KB Output is correct
43 Correct 110 ms 118468 KB Output is correct
44 Correct 105 ms 117608 KB Output is correct
45 Correct 106 ms 118308 KB Output is correct
46 Correct 106 ms 118204 KB Output is correct
47 Correct 104 ms 117436 KB Output is correct
48 Correct 107 ms 118208 KB Output is correct
49 Correct 110 ms 116928 KB Output is correct
50 Correct 105 ms 117656 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 21 ms 107096 KB Output is correct
3 Correct 21 ms 107100 KB Output is correct
4 Correct 21 ms 107028 KB Output is correct
5 Correct 22 ms 107100 KB Output is correct
6 Correct 21 ms 107100 KB Output is correct
7 Correct 22 ms 106944 KB Output is correct
8 Correct 21 ms 107100 KB Output is correct
9 Correct 21 ms 107100 KB Output is correct
10 Correct 22 ms 107100 KB Output is correct
11 Correct 22 ms 106980 KB Output is correct
12 Correct 22 ms 107096 KB Output is correct
13 Correct 22 ms 107100 KB Output is correct
14 Correct 21 ms 107100 KB Output is correct
15 Correct 22 ms 107008 KB Output is correct
16 Correct 23 ms 107096 KB Output is correct
17 Correct 22 ms 107096 KB Output is correct
18 Correct 22 ms 107100 KB Output is correct
19 Correct 25 ms 107356 KB Output is correct
20 Correct 25 ms 107320 KB Output is correct
21 Correct 25 ms 107424 KB Output is correct
22 Correct 26 ms 107824 KB Output is correct
23 Correct 30 ms 108392 KB Output is correct
24 Correct 26 ms 107612 KB Output is correct
25 Correct 25 ms 107580 KB Output is correct
26 Correct 25 ms 107776 KB Output is correct
27 Correct 359 ms 121528 KB Output is correct
28 Correct 398 ms 121672 KB Output is correct
29 Correct 354 ms 120800 KB Output is correct
30 Correct 356 ms 122448 KB Output is correct
31 Correct 314 ms 121272 KB Output is correct
32 Correct 357 ms 131764 KB Output is correct
33 Correct 356 ms 124792 KB Output is correct
34 Correct 353 ms 127140 KB Output is correct
35 Correct 21 ms 107064 KB Output is correct
36 Correct 274 ms 133756 KB Output is correct
37 Correct 936 ms 188172 KB Output is correct
38 Correct 967 ms 186212 KB Output is correct
39 Correct 1177 ms 185220 KB Output is correct
40 Correct 394 ms 137920 KB Output is correct
41 Correct 149 ms 120488 KB Output is correct
42 Correct 37 ms 110796 KB Output is correct
43 Correct 1024 ms 189640 KB Output is correct
44 Correct 1585 ms 180092 KB Output is correct
45 Correct 689 ms 178612 KB Output is correct
46 Correct 302 ms 142572 KB Output is correct
47 Correct 717 ms 128636 KB Output is correct
48 Correct 346 ms 146788 KB Output is correct
49 Correct 328 ms 144496 KB Output is correct
50 Correct 568 ms 123060 KB Output is correct
51 Correct 30 ms 109660 KB Output is correct
52 Correct 31 ms 109568 KB Output is correct
53 Correct 32 ms 109392 KB Output is correct
54 Correct 34 ms 111188 KB Output is correct
55 Correct 31 ms 110548 KB Output is correct
56 Correct 30 ms 110424 KB Output is correct
57 Correct 131 ms 111508 KB Output is correct
58 Correct 111 ms 111472 KB Output is correct
59 Correct 120 ms 111560 KB Output is correct
60 Correct 168 ms 124100 KB Output is correct
61 Correct 181 ms 124524 KB Output is correct
62 Correct 176 ms 126740 KB Output is correct
63 Correct 143 ms 112324 KB Output is correct
64 Correct 137 ms 112116 KB Output is correct
65 Correct 134 ms 112160 KB Output is correct
66 Correct 139 ms 112576 KB Output is correct
67 Correct 110 ms 118468 KB Output is correct
68 Correct 105 ms 117608 KB Output is correct
69 Correct 106 ms 118308 KB Output is correct
70 Correct 106 ms 118204 KB Output is correct
71 Correct 104 ms 117436 KB Output is correct
72 Correct 107 ms 118208 KB Output is correct
73 Correct 110 ms 116928 KB Output is correct
74 Correct 105 ms 117656 KB Output is correct
75 Correct 380 ms 121860 KB Output is correct
76 Correct 377 ms 121924 KB Output is correct
77 Correct 342 ms 122040 KB Output is correct
78 Correct 366 ms 120932 KB Output is correct
79 Correct 432 ms 121508 KB Output is correct
80 Correct 351 ms 121236 KB Output is correct
81 Correct 848 ms 183228 KB Output is correct
82 Correct 706 ms 173680 KB Output is correct
83 Correct 720 ms 173976 KB Output is correct
84 Correct 1155 ms 196992 KB Output is correct
85 Correct 795 ms 179616 KB Output is correct
86 Correct 689 ms 171188 KB Output is correct
87 Correct 2633 ms 240992 KB Output is correct
88 Correct 414 ms 123576 KB Output is correct
89 Correct 418 ms 124348 KB Output is correct
90 Correct 458 ms 125048 KB Output is correct
91 Correct 414 ms 123728 KB Output is correct
92 Correct 415 ms 123432 KB Output is correct
93 Correct 343 ms 142324 KB Output is correct
94 Correct 2634 ms 191608 KB Output is correct
95 Correct 344 ms 143348 KB Output is correct
96 Correct 362 ms 143540 KB Output is correct
97 Correct 2233 ms 167908 KB Output is correct
98 Correct 446 ms 135612 KB Output is correct
99 Correct 392 ms 142004 KB Output is correct
100 Correct 327 ms 143284 KB Output is correct
101 Correct 494 ms 146788 KB Output is correct
102 Correct 351 ms 143176 KB Output is correct
103 Execution timed out 3057 ms 186368 KB Time limit exceeded
104 Halted 0 ms 0 KB -