oj.uz

Submission #851452

# Submission time Handle Problem Language Result Execution time Memory
851452 2023-09-19T19:50:51 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 230664 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int INF = 1010101010;
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;

	SegTree(int _n) : n(_n) {
		for (base = 1; base < n; base <<= 1);
		T.resize(base + base);
	}

	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) {
		p += base; p--;
		vector<pair<int, set<pii>::iterator>> v;
		while (p >= 1) {
			v.emplace_back(p, T[p].s.lower_bound({y, 0}));
			p >>= 1;
		}
		pii m1, m2;
		m1 = m2 = {INF, 0};
		for (auto j : v) {
			int p = j.first;
			auto it = j.second;
			if (it == T[p].s.end()) continue;
			if (*it <= m1) {
				m2 = m1; m1 = *it;
				if (m1.first <= (long long)y + r + r && next(it) != T[p].s.end()) m2 = min(m2, *next(it));
			} else if (m1.first <= (long long)y + r + r) {
				m2 = min(m2, *it);
			}
		}
		if (m1.first != INF) chk(m1.second);
		if (m2.first != INF) chk(m2.second);
		m1 = m2 = {-INF, 0};
		for (auto j : v) {
			int p = j.first;
			auto it = j.second;
			if (it == T[p].s.begin()) continue;
			auto pit = prev(it);
			if (*pit >= m1) {
				m2 = m1; m1 = *pit;
				if (m1.first >= (long long)y - r - r && pit != T[p].s.begin()) m2 = max(m2, *prev(pit));
			} else if (m1.first >= (long long)y - r - r) {
				m2 = max(m2, *pit);
			}
		}
		if (m1.first != -INF) chk(m1.second);
		if (m2.first != -INF) chk(m2.second);
	}
};

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]);
		seg.get(XR[i], Y[i], R[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:135:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  135 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:135:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  135 |  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 6604 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 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 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 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 6 ms 8284 KB Output is correct
22 Correct 6 ms 8796 KB Output is correct
23 Correct 12 ms 9304 KB Output is correct
24 Correct 6 ms 8540 KB Output is correct
25 Correct 6 ms 8284 KB Output is correct
26 Correct 6 ms 8536 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 113012 KB Output is correct
2 Correct 549 ms 112056 KB Output is correct
3 Correct 564 ms 111412 KB Output is correct
4 Correct 508 ms 112344 KB Output is correct
5 Correct 531 ms 63732 KB Output is correct
6 Correct 541 ms 123084 KB Output is correct
7 Correct 519 ms 114396 KB Output is correct
8 Correct 537 ms 117728 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 324 ms 55196 KB Output is correct
3 Correct 1218 ms 177820 KB Output is correct
4 Correct 1212 ms 177180 KB Output is correct
5 Correct 1459 ms 175696 KB Output is correct
6 Correct 569 ms 81944 KB Output is correct
7 Correct 200 ms 42224 KB Output is correct
8 Correct 22 ms 14036 KB Output is correct
9 Correct 1356 ms 180132 KB Output is correct
10 Correct 1771 ms 170356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 169724 KB Output is correct
2 Correct 413 ms 133612 KB Output is correct
3 Correct 882 ms 119156 KB Output is correct
4 Correct 456 ms 138112 KB Output is correct
5 Correct 423 ms 135308 KB Output is correct
6 Correct 750 ms 113144 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 6604 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 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 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 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 6 ms 8284 KB Output is correct
22 Correct 6 ms 8796 KB Output is correct
23 Correct 12 ms 9304 KB Output is correct
24 Correct 6 ms 8540 KB Output is correct
25 Correct 6 ms 8284 KB Output is correct
26 Correct 6 ms 8536 KB Output is correct
27 Correct 12 ms 9820 KB Output is correct
28 Correct 10 ms 9820 KB Output is correct
29 Correct 10 ms 9936 KB Output is correct
30 Correct 15 ms 11612 KB Output is correct
31 Correct 12 ms 10840 KB Output is correct
32 Correct 11 ms 10844 KB Output is correct
33 Correct 118 ms 33164 KB Output is correct
34 Correct 121 ms 33076 KB Output is correct
35 Correct 130 ms 33112 KB Output is correct
36 Correct 180 ms 46076 KB Output is correct
37 Correct 196 ms 46108 KB Output is correct
38 Correct 251 ms 48660 KB Output is correct
39 Correct 150 ms 11504 KB Output is correct
40 Correct 143 ms 11588 KB Output is correct
41 Correct 151 ms 11700 KB Output is correct
42 Correct 148 ms 11712 KB Output is correct
43 Correct 121 ms 40032 KB Output is correct
44 Correct 129 ms 39360 KB Output is correct
45 Correct 119 ms 39980 KB Output is correct
46 Correct 120 ms 39704 KB Output is correct
47 Correct 122 ms 39020 KB Output is correct
48 Correct 134 ms 40176 KB Output is correct
49 Correct 124 ms 38820 KB Output is correct
50 Correct 123 ms 39348 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 6604 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 6488 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 6748 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 8284 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 6 ms 8284 KB Output is correct
22 Correct 6 ms 8796 KB Output is correct
23 Correct 12 ms 9304 KB Output is correct
24 Correct 6 ms 8540 KB Output is correct
25 Correct 6 ms 8284 KB Output is correct
26 Correct 6 ms 8536 KB Output is correct
27 Correct 524 ms 113012 KB Output is correct
28 Correct 549 ms 112056 KB Output is correct
29 Correct 564 ms 111412 KB Output is correct
30 Correct 508 ms 112344 KB Output is correct
31 Correct 531 ms 63732 KB Output is correct
32 Correct 541 ms 123084 KB Output is correct
33 Correct 519 ms 114396 KB Output is correct
34 Correct 537 ms 117728 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 324 ms 55196 KB Output is correct
37 Correct 1218 ms 177820 KB Output is correct
38 Correct 1212 ms 177180 KB Output is correct
39 Correct 1459 ms 175696 KB Output is correct
40 Correct 569 ms 81944 KB Output is correct
41 Correct 200 ms 42224 KB Output is correct
42 Correct 22 ms 14036 KB Output is correct
43 Correct 1356 ms 180132 KB Output is correct
44 Correct 1771 ms 170356 KB Output is correct
45 Correct 933 ms 169724 KB Output is correct
46 Correct 413 ms 133612 KB Output is correct
47 Correct 882 ms 119156 KB Output is correct
48 Correct 456 ms 138112 KB Output is correct
49 Correct 423 ms 135308 KB Output is correct
50 Correct 750 ms 113144 KB Output is correct
51 Correct 12 ms 9820 KB Output is correct
52 Correct 10 ms 9820 KB Output is correct
53 Correct 10 ms 9936 KB Output is correct
54 Correct 15 ms 11612 KB Output is correct
55 Correct 12 ms 10840 KB Output is correct
56 Correct 11 ms 10844 KB Output is correct
57 Correct 118 ms 33164 KB Output is correct
58 Correct 121 ms 33076 KB Output is correct
59 Correct 130 ms 33112 KB Output is correct
60 Correct 180 ms 46076 KB Output is correct
61 Correct 196 ms 46108 KB Output is correct
62 Correct 251 ms 48660 KB Output is correct
63 Correct 150 ms 11504 KB Output is correct
64 Correct 143 ms 11588 KB Output is correct
65 Correct 151 ms 11700 KB Output is correct
66 Correct 148 ms 11712 KB Output is correct
67 Correct 121 ms 40032 KB Output is correct
68 Correct 129 ms 39360 KB Output is correct
69 Correct 119 ms 39980 KB Output is correct
70 Correct 120 ms 39704 KB Output is correct
71 Correct 122 ms 39020 KB Output is correct
72 Correct 134 ms 40176 KB Output is correct
73 Correct 124 ms 38820 KB Output is correct
74 Correct 123 ms 39348 KB Output is correct
75 Correct 543 ms 111624 KB Output is correct
76 Correct 515 ms 113136 KB Output is correct
77 Correct 425 ms 113032 KB Output is correct
78 Correct 493 ms 113036 KB Output is correct
79 Correct 651 ms 112620 KB Output is correct
80 Correct 490 ms 111292 KB Output is correct
81 Correct 1133 ms 172836 KB Output is correct
82 Correct 990 ms 164224 KB Output is correct
83 Correct 989 ms 165268 KB Output is correct
84 Correct 1529 ms 189324 KB Output is correct
85 Correct 1068 ms 170188 KB Output is correct
86 Correct 959 ms 162672 KB Output is correct
87 Correct 2858 ms 230664 KB Output is correct
88 Correct 517 ms 22652 KB Output is correct
89 Correct 510 ms 22844 KB Output is correct
90 Correct 489 ms 22968 KB Output is correct
91 Correct 506 ms 21860 KB Output is correct
92 Correct 521 ms 23492 KB Output is correct
93 Correct 479 ms 134840 KB Output is correct
94 Execution timed out 3022 ms 90196 KB Time limit exceeded
95 Halted 0 ms 0 KB -