oj.uz

Submission #851591

# Submission time Handle Problem Language Result Execution time Memory
851591 2023-09-20T07:55:18 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 243724 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
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<ll> 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];
	}

	inline ll cvt(pii x) { return (ll)x.first * N + x.second - 1; }

	void chk_node(int idx, int y, int r) {
		auto it = T[idx].s.lower_bound(cvt({y, 1}));
		auto tmp = it;
		for (int i = 0; i < K; i++) {
			if (it == T[idx].s.end()) break;
			ll q = *it / N, j = *it % N;
			if (j < 0) { j += N; q--; }
			chk(j + 1);
			if (q >= (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--;
			ll q = *it / N, j = *it % N;
			if (j < 0) { j += N; q--; }
			chk(j + 1);
			if (q <= (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(cvt(x));
			if (~q & 1) T[q--].s.insert(cvt(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:133:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  133 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:133:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  133 |  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 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 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 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6588 KB Output is correct
16 Correct 2 ms 6860 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8536 KB Output is correct
20 Correct 5 ms 8540 KB Output is correct
21 Correct 5 ms 8540 KB Output is correct
22 Correct 5 ms 9052 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8904 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 6 ms 8796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 119648 KB Output is correct
2 Correct 374 ms 120044 KB Output is correct
3 Correct 375 ms 121288 KB Output is correct
4 Correct 373 ms 120724 KB Output is correct
5 Correct 310 ms 68024 KB Output is correct
6 Correct 404 ms 131188 KB Output is correct
7 Correct 354 ms 123952 KB Output is correct
8 Correct 357 ms 124532 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 298 ms 58960 KB Output is correct
3 Correct 977 ms 189820 KB Output is correct
4 Correct 979 ms 190500 KB Output is correct
5 Correct 1315 ms 188968 KB Output is correct
6 Correct 505 ms 88144 KB Output is correct
7 Correct 154 ms 45636 KB Output is correct
8 Correct 16 ms 15060 KB Output is correct
9 Correct 1104 ms 192984 KB Output is correct
10 Correct 1670 ms 183016 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 176972 KB Output is correct
2 Correct 317 ms 144920 KB Output is correct
3 Correct 714 ms 132364 KB Output is correct
4 Correct 354 ms 149576 KB Output is correct
5 Correct 345 ms 146292 KB Output is correct
6 Correct 605 ms 126892 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 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 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 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6588 KB Output is correct
16 Correct 2 ms 6860 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8536 KB Output is correct
20 Correct 5 ms 8540 KB Output is correct
21 Correct 5 ms 8540 KB Output is correct
22 Correct 5 ms 9052 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8904 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 6 ms 8796 KB Output is correct
27 Correct 8 ms 10584 KB Output is correct
28 Correct 9 ms 10512 KB Output is correct
29 Correct 10 ms 10332 KB Output is correct
30 Correct 13 ms 12124 KB Output is correct
31 Correct 11 ms 11224 KB Output is correct
32 Correct 9 ms 11352 KB Output is correct
33 Correct 94 ms 36940 KB Output is correct
34 Correct 97 ms 36804 KB Output is correct
35 Correct 112 ms 36920 KB Output is correct
36 Correct 147 ms 49448 KB Output is correct
37 Correct 146 ms 49728 KB Output is correct
38 Correct 192 ms 51924 KB Output is correct
39 Correct 115 ms 12232 KB Output is correct
40 Correct 122 ms 12232 KB Output is correct
41 Correct 116 ms 12224 KB Output is correct
42 Correct 120 ms 12884 KB Output is correct
43 Correct 104 ms 43536 KB Output is correct
44 Correct 96 ms 42868 KB Output is correct
45 Correct 97 ms 43460 KB Output is correct
46 Correct 94 ms 43356 KB Output is correct
47 Correct 99 ms 42600 KB Output is correct
48 Correct 98 ms 43360 KB Output is correct
49 Correct 99 ms 42136 KB Output is correct
50 Correct 96 ms 42844 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 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 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 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6588 KB Output is correct
16 Correct 2 ms 6860 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 5 ms 8536 KB Output is correct
20 Correct 5 ms 8540 KB Output is correct
21 Correct 5 ms 8540 KB Output is correct
22 Correct 5 ms 9052 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 5 ms 8904 KB Output is correct
25 Correct 5 ms 8540 KB Output is correct
26 Correct 6 ms 8796 KB Output is correct
27 Correct 375 ms 119648 KB Output is correct
28 Correct 374 ms 120044 KB Output is correct
29 Correct 375 ms 121288 KB Output is correct
30 Correct 373 ms 120724 KB Output is correct
31 Correct 310 ms 68024 KB Output is correct
32 Correct 404 ms 131188 KB Output is correct
33 Correct 354 ms 123952 KB Output is correct
34 Correct 357 ms 124532 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 298 ms 58960 KB Output is correct
37 Correct 977 ms 189820 KB Output is correct
38 Correct 979 ms 190500 KB Output is correct
39 Correct 1315 ms 188968 KB Output is correct
40 Correct 505 ms 88144 KB Output is correct
41 Correct 154 ms 45636 KB Output is correct
42 Correct 16 ms 15060 KB Output is correct
43 Correct 1104 ms 192984 KB Output is correct
44 Correct 1670 ms 183016 KB Output is correct
45 Correct 700 ms 176972 KB Output is correct
46 Correct 317 ms 144920 KB Output is correct
47 Correct 714 ms 132364 KB Output is correct
48 Correct 354 ms 149576 KB Output is correct
49 Correct 345 ms 146292 KB Output is correct
50 Correct 605 ms 126892 KB Output is correct
51 Correct 8 ms 10584 KB Output is correct
52 Correct 9 ms 10512 KB Output is correct
53 Correct 10 ms 10332 KB Output is correct
54 Correct 13 ms 12124 KB Output is correct
55 Correct 11 ms 11224 KB Output is correct
56 Correct 9 ms 11352 KB Output is correct
57 Correct 94 ms 36940 KB Output is correct
58 Correct 97 ms 36804 KB Output is correct
59 Correct 112 ms 36920 KB Output is correct
60 Correct 147 ms 49448 KB Output is correct
61 Correct 146 ms 49728 KB Output is correct
62 Correct 192 ms 51924 KB Output is correct
63 Correct 115 ms 12232 KB Output is correct
64 Correct 122 ms 12232 KB Output is correct
65 Correct 116 ms 12224 KB Output is correct
66 Correct 120 ms 12884 KB Output is correct
67 Correct 104 ms 43536 KB Output is correct
68 Correct 96 ms 42868 KB Output is correct
69 Correct 97 ms 43460 KB Output is correct
70 Correct 94 ms 43356 KB Output is correct
71 Correct 99 ms 42600 KB Output is correct
72 Correct 98 ms 43360 KB Output is correct
73 Correct 99 ms 42136 KB Output is correct
74 Correct 96 ms 42844 KB Output is correct
75 Correct 412 ms 124340 KB Output is correct
76 Correct 402 ms 125700 KB Output is correct
77 Correct 386 ms 125012 KB Output is correct
78 Correct 380 ms 124324 KB Output is correct
79 Correct 500 ms 125644 KB Output is correct
80 Correct 395 ms 125536 KB Output is correct
81 Correct 973 ms 186064 KB Output is correct
82 Correct 771 ms 176272 KB Output is correct
83 Correct 845 ms 177084 KB Output is correct
84 Correct 1300 ms 199808 KB Output is correct
85 Correct 917 ms 181400 KB Output is correct
86 Correct 755 ms 174240 KB Output is correct
87 Correct 2936 ms 243724 KB Output is correct
88 Correct 432 ms 23872 KB Output is correct
89 Correct 468 ms 24096 KB Output is correct
90 Correct 457 ms 25268 KB Output is correct
91 Correct 406 ms 25488 KB Output is correct
92 Correct 404 ms 25172 KB Output is correct
93 Correct 349 ms 144912 KB Output is correct
94 Execution timed out 3084 ms 94132 KB Time limit exceeded
95 Halted 0 ms 0 KB -