oj.uz

Submission #851458

# Submission time Handle Problem Language Result Execution time Memory
851458 2023-09-19T20:21:19 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 240244 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 idx, int y, int r) {
		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 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], 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 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 6488 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6596 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 Correct 1 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 4 ms 8272 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 8792 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8668 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 120052 KB Output is correct
2 Correct 379 ms 121324 KB Output is correct
3 Correct 368 ms 119720 KB Output is correct
4 Correct 368 ms 121420 KB Output is correct
5 Correct 303 ms 67440 KB Output is correct
6 Correct 369 ms 131764 KB Output is correct
7 Correct 365 ms 122708 KB Output is correct
8 Correct 359 ms 125688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 267 ms 57364 KB Output is correct
3 Correct 954 ms 186552 KB Output is correct
4 Correct 977 ms 185080 KB Output is correct
5 Correct 1220 ms 183396 KB Output is correct
6 Correct 434 ms 85848 KB Output is correct
7 Correct 132 ms 44228 KB Output is correct
8 Correct 16 ms 14548 KB Output is correct
9 Correct 1061 ms 189208 KB Output is correct
10 Correct 1538 ms 178808 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 177844 KB Output is correct
2 Correct 322 ms 142012 KB Output is correct
3 Correct 669 ms 127160 KB Output is correct
4 Correct 358 ms 145612 KB Output is correct
5 Correct 342 ms 143544 KB Output is correct
6 Correct 583 ms 122032 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 6488 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6596 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 Correct 1 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 4 ms 8272 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 8792 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8668 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8996 KB Output is correct
27 Correct 8 ms 10328 KB Output is correct
28 Correct 8 ms 10072 KB Output is correct
29 Correct 9 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 11100 KB Output is correct
33 Correct 92 ms 35008 KB Output is correct
34 Correct 99 ms 35128 KB Output is correct
35 Correct 106 ms 35008 KB Output is correct
36 Correct 143 ms 47812 KB Output is correct
37 Correct 147 ms 48200 KB Output is correct
38 Correct 178 ms 50880 KB Output is correct
39 Correct 111 ms 11452 KB Output is correct
40 Correct 111 ms 11460 KB Output is correct
41 Correct 109 ms 11612 KB Output is correct
42 Correct 118 ms 11716 KB Output is correct
43 Correct 94 ms 42072 KB Output is correct
44 Correct 91 ms 41220 KB Output is correct
45 Correct 93 ms 41816 KB Output is correct
46 Correct 108 ms 41968 KB Output is correct
47 Correct 92 ms 40908 KB Output is correct
48 Correct 91 ms 41920 KB Output is correct
49 Correct 91 ms 40644 KB Output is correct
50 Correct 94 ms 41412 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 6488 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6596 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 Correct 1 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 4 ms 8272 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 8792 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8668 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 5 ms 8996 KB Output is correct
27 Correct 380 ms 120052 KB Output is correct
28 Correct 379 ms 121324 KB Output is correct
29 Correct 368 ms 119720 KB Output is correct
30 Correct 368 ms 121420 KB Output is correct
31 Correct 303 ms 67440 KB Output is correct
32 Correct 369 ms 131764 KB Output is correct
33 Correct 365 ms 122708 KB Output is correct
34 Correct 359 ms 125688 KB Output is correct
35 Correct 1 ms 6488 KB Output is correct
36 Correct 267 ms 57364 KB Output is correct
37 Correct 954 ms 186552 KB Output is correct
38 Correct 977 ms 185080 KB Output is correct
39 Correct 1220 ms 183396 KB Output is correct
40 Correct 434 ms 85848 KB Output is correct
41 Correct 132 ms 44228 KB Output is correct
42 Correct 16 ms 14548 KB Output is correct
43 Correct 1061 ms 189208 KB Output is correct
44 Correct 1538 ms 178808 KB Output is correct
45 Correct 667 ms 177844 KB Output is correct
46 Correct 322 ms 142012 KB Output is correct
47 Correct 669 ms 127160 KB Output is correct
48 Correct 358 ms 145612 KB Output is correct
49 Correct 342 ms 143544 KB Output is correct
50 Correct 583 ms 122032 KB Output is correct
51 Correct 8 ms 10328 KB Output is correct
52 Correct 8 ms 10072 KB Output is correct
53 Correct 9 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 11100 KB Output is correct
57 Correct 92 ms 35008 KB Output is correct
58 Correct 99 ms 35128 KB Output is correct
59 Correct 106 ms 35008 KB Output is correct
60 Correct 143 ms 47812 KB Output is correct
61 Correct 147 ms 48200 KB Output is correct
62 Correct 178 ms 50880 KB Output is correct
63 Correct 111 ms 11452 KB Output is correct
64 Correct 111 ms 11460 KB Output is correct
65 Correct 109 ms 11612 KB Output is correct
66 Correct 118 ms 11716 KB Output is correct
67 Correct 94 ms 42072 KB Output is correct
68 Correct 91 ms 41220 KB Output is correct
69 Correct 93 ms 41816 KB Output is correct
70 Correct 108 ms 41968 KB Output is correct
71 Correct 92 ms 40908 KB Output is correct
72 Correct 91 ms 41920 KB Output is correct
73 Correct 91 ms 40644 KB Output is correct
74 Correct 94 ms 41412 KB Output is correct
75 Correct 385 ms 120076 KB Output is correct
76 Correct 388 ms 121428 KB Output is correct
77 Correct 341 ms 120968 KB Output is correct
78 Correct 364 ms 119960 KB Output is correct
79 Correct 469 ms 121384 KB Output is correct
80 Correct 365 ms 120244 KB Output is correct
81 Correct 854 ms 181260 KB Output is correct
82 Correct 728 ms 172324 KB Output is correct
83 Correct 748 ms 171924 KB Output is correct
84 Correct 1190 ms 197300 KB Output is correct
85 Correct 807 ms 177268 KB Output is correct
86 Correct 696 ms 169908 KB Output is correct
87 Correct 2665 ms 240244 KB Output is correct
88 Correct 402 ms 23304 KB Output is correct
89 Correct 412 ms 23804 KB Output is correct
90 Correct 398 ms 22116 KB Output is correct
91 Correct 424 ms 23676 KB Output is correct
92 Correct 396 ms 22200 KB Output is correct
93 Correct 351 ms 141204 KB Output is correct
94 Execution timed out 3040 ms 91380 KB Time limit exceeded
95 Halted 0 ms 0 KB -