oj.uz

답안 #851387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851387 2023-09-19T17:22:53 Z dlalswp25 원 고르기 (APIO18_circle_selection) C++17
87 / 100
 3000 ms 239840 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;
set<pii> T[2121212];
 
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 chk_node(int idx, int y, int r) {
		auto it = T[idx].lower_bound({y, 0});
		auto tmp = it;
		for (int i = 0; i < K; i++) {
			if (it == T[idx].end()) break;
			chk(it->second);
			if (it->first >= y + r) break;
			if (i < K - 1) it++;
		}
		it = tmp;
		for (int i = 0; i < K; i++) {
			if (it == T[idx].begin()) break;
			it--;
			chk(it->second);
			if (it->first <= y - 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) {
		p += base; p--;
		while (p >= 1) {
			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]);
		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:122:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  122 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:122:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  122 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 105048 KB Output is correct
2 Correct 23 ms 105236 KB Output is correct
3 Correct 19 ms 105048 KB Output is correct
4 Correct 20 ms 105308 KB Output is correct
5 Correct 21 ms 105052 KB Output is correct
6 Correct 20 ms 105048 KB Output is correct
7 Correct 21 ms 105048 KB Output is correct
8 Correct 20 ms 105048 KB Output is correct
9 Correct 22 ms 105300 KB Output is correct
10 Correct 20 ms 105048 KB Output is correct
11 Correct 20 ms 105184 KB Output is correct
12 Correct 21 ms 105048 KB Output is correct
13 Correct 20 ms 105448 KB Output is correct
14 Correct 21 ms 105180 KB Output is correct
15 Correct 20 ms 105052 KB Output is correct
16 Correct 20 ms 105240 KB Output is correct
17 Correct 22 ms 105308 KB Output is correct
18 Correct 20 ms 105316 KB Output is correct
19 Correct 23 ms 105572 KB Output is correct
20 Correct 23 ms 105572 KB Output is correct
21 Correct 23 ms 105560 KB Output is correct
22 Correct 26 ms 105832 KB Output is correct
23 Correct 30 ms 106676 KB Output is correct
24 Correct 24 ms 105832 KB Output is correct
25 Correct 26 ms 105560 KB Output is correct
26 Correct 26 ms 105816 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 120444 KB Output is correct
2 Correct 364 ms 120808 KB Output is correct
3 Correct 362 ms 119476 KB Output is correct
4 Correct 359 ms 120532 KB Output is correct
5 Correct 319 ms 119188 KB Output is correct
6 Correct 407 ms 129596 KB Output is correct
7 Correct 377 ms 121588 KB Output is correct
8 Correct 376 ms 122628 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 105048 KB Output is correct
2 Correct 288 ms 132296 KB Output is correct
3 Correct 1000 ms 188020 KB Output is correct
4 Correct 1000 ms 187244 KB Output is correct
5 Correct 1344 ms 184800 KB Output is correct
6 Correct 451 ms 136024 KB Output is correct
7 Correct 151 ms 118572 KB Output is correct
8 Correct 39 ms 106956 KB Output is correct
9 Correct 1053 ms 190568 KB Output is correct
10 Correct 1678 ms 180496 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 689 ms 177692 KB Output is correct
2 Correct 334 ms 142052 KB Output is correct
3 Correct 685 ms 129776 KB Output is correct
4 Correct 367 ms 145640 KB Output is correct
5 Correct 353 ms 144368 KB Output is correct
6 Correct 660 ms 123128 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 105048 KB Output is correct
2 Correct 23 ms 105236 KB Output is correct
3 Correct 19 ms 105048 KB Output is correct
4 Correct 20 ms 105308 KB Output is correct
5 Correct 21 ms 105052 KB Output is correct
6 Correct 20 ms 105048 KB Output is correct
7 Correct 21 ms 105048 KB Output is correct
8 Correct 20 ms 105048 KB Output is correct
9 Correct 22 ms 105300 KB Output is correct
10 Correct 20 ms 105048 KB Output is correct
11 Correct 20 ms 105184 KB Output is correct
12 Correct 21 ms 105048 KB Output is correct
13 Correct 20 ms 105448 KB Output is correct
14 Correct 21 ms 105180 KB Output is correct
15 Correct 20 ms 105052 KB Output is correct
16 Correct 20 ms 105240 KB Output is correct
17 Correct 22 ms 105308 KB Output is correct
18 Correct 20 ms 105316 KB Output is correct
19 Correct 23 ms 105572 KB Output is correct
20 Correct 23 ms 105572 KB Output is correct
21 Correct 23 ms 105560 KB Output is correct
22 Correct 26 ms 105832 KB Output is correct
23 Correct 30 ms 106676 KB Output is correct
24 Correct 24 ms 105832 KB Output is correct
25 Correct 26 ms 105560 KB Output is correct
26 Correct 26 ms 105816 KB Output is correct
27 Correct 30 ms 105808 KB Output is correct
28 Correct 28 ms 105812 KB Output is correct
29 Correct 28 ms 105784 KB Output is correct
30 Correct 32 ms 107332 KB Output is correct
31 Correct 30 ms 106584 KB Output is correct
32 Correct 35 ms 106668 KB Output is correct
33 Correct 110 ms 110436 KB Output is correct
34 Correct 108 ms 110276 KB Output is correct
35 Correct 124 ms 110284 KB Output is correct
36 Correct 173 ms 122492 KB Output is correct
37 Correct 176 ms 123180 KB Output is correct
38 Correct 227 ms 125364 KB Output is correct
39 Correct 137 ms 111496 KB Output is correct
40 Correct 140 ms 111488 KB Output is correct
41 Correct 132 ms 111792 KB Output is correct
42 Correct 141 ms 112068 KB Output is correct
43 Correct 111 ms 116928 KB Output is correct
44 Correct 106 ms 116160 KB Output is correct
45 Correct 107 ms 117108 KB Output is correct
46 Correct 110 ms 116564 KB Output is correct
47 Correct 116 ms 115828 KB Output is correct
48 Correct 116 ms 116764 KB Output is correct
49 Correct 116 ms 115656 KB Output is correct
50 Correct 111 ms 116340 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 105048 KB Output is correct
2 Correct 23 ms 105236 KB Output is correct
3 Correct 19 ms 105048 KB Output is correct
4 Correct 20 ms 105308 KB Output is correct
5 Correct 21 ms 105052 KB Output is correct
6 Correct 20 ms 105048 KB Output is correct
7 Correct 21 ms 105048 KB Output is correct
8 Correct 20 ms 105048 KB Output is correct
9 Correct 22 ms 105300 KB Output is correct
10 Correct 20 ms 105048 KB Output is correct
11 Correct 20 ms 105184 KB Output is correct
12 Correct 21 ms 105048 KB Output is correct
13 Correct 20 ms 105448 KB Output is correct
14 Correct 21 ms 105180 KB Output is correct
15 Correct 20 ms 105052 KB Output is correct
16 Correct 20 ms 105240 KB Output is correct
17 Correct 22 ms 105308 KB Output is correct
18 Correct 20 ms 105316 KB Output is correct
19 Correct 23 ms 105572 KB Output is correct
20 Correct 23 ms 105572 KB Output is correct
21 Correct 23 ms 105560 KB Output is correct
22 Correct 26 ms 105832 KB Output is correct
23 Correct 30 ms 106676 KB Output is correct
24 Correct 24 ms 105832 KB Output is correct
25 Correct 26 ms 105560 KB Output is correct
26 Correct 26 ms 105816 KB Output is correct
27 Correct 382 ms 120444 KB Output is correct
28 Correct 364 ms 120808 KB Output is correct
29 Correct 362 ms 119476 KB Output is correct
30 Correct 359 ms 120532 KB Output is correct
31 Correct 319 ms 119188 KB Output is correct
32 Correct 407 ms 129596 KB Output is correct
33 Correct 377 ms 121588 KB Output is correct
34 Correct 376 ms 122628 KB Output is correct
35 Correct 22 ms 105048 KB Output is correct
36 Correct 288 ms 132296 KB Output is correct
37 Correct 1000 ms 188020 KB Output is correct
38 Correct 1000 ms 187244 KB Output is correct
39 Correct 1344 ms 184800 KB Output is correct
40 Correct 451 ms 136024 KB Output is correct
41 Correct 151 ms 118572 KB Output is correct
42 Correct 39 ms 106956 KB Output is correct
43 Correct 1053 ms 190568 KB Output is correct
44 Correct 1678 ms 180496 KB Output is correct
45 Correct 689 ms 177692 KB Output is correct
46 Correct 334 ms 142052 KB Output is correct
47 Correct 685 ms 129776 KB Output is correct
48 Correct 367 ms 145640 KB Output is correct
49 Correct 353 ms 144368 KB Output is correct
50 Correct 660 ms 123128 KB Output is correct
51 Correct 30 ms 105808 KB Output is correct
52 Correct 28 ms 105812 KB Output is correct
53 Correct 28 ms 105784 KB Output is correct
54 Correct 32 ms 107332 KB Output is correct
55 Correct 30 ms 106584 KB Output is correct
56 Correct 35 ms 106668 KB Output is correct
57 Correct 110 ms 110436 KB Output is correct
58 Correct 108 ms 110276 KB Output is correct
59 Correct 124 ms 110284 KB Output is correct
60 Correct 173 ms 122492 KB Output is correct
61 Correct 176 ms 123180 KB Output is correct
62 Correct 227 ms 125364 KB Output is correct
63 Correct 137 ms 111496 KB Output is correct
64 Correct 140 ms 111488 KB Output is correct
65 Correct 132 ms 111792 KB Output is correct
66 Correct 141 ms 112068 KB Output is correct
67 Correct 111 ms 116928 KB Output is correct
68 Correct 106 ms 116160 KB Output is correct
69 Correct 107 ms 117108 KB Output is correct
70 Correct 110 ms 116564 KB Output is correct
71 Correct 116 ms 115828 KB Output is correct
72 Correct 116 ms 116764 KB Output is correct
73 Correct 116 ms 115656 KB Output is correct
74 Correct 111 ms 116340 KB Output is correct
75 Correct 432 ms 123312 KB Output is correct
76 Correct 366 ms 121860 KB Output is correct
77 Correct 331 ms 122380 KB Output is correct
78 Correct 368 ms 122024 KB Output is correct
79 Correct 480 ms 122548 KB Output is correct
80 Correct 384 ms 122528 KB Output is correct
81 Correct 904 ms 181720 KB Output is correct
82 Correct 772 ms 173360 KB Output is correct
83 Correct 788 ms 172640 KB Output is correct
84 Correct 1323 ms 198300 KB Output is correct
85 Correct 899 ms 178444 KB Output is correct
86 Correct 755 ms 170752 KB Output is correct
87 Correct 2861 ms 239840 KB Output is correct
88 Correct 506 ms 125320 KB Output is correct
89 Correct 435 ms 126216 KB Output is correct
90 Correct 494 ms 124852 KB Output is correct
91 Correct 425 ms 125944 KB Output is correct
92 Correct 450 ms 124868 KB Output is correct
93 Correct 338 ms 141492 KB Output is correct
94 Correct 2901 ms 198088 KB Output is correct
95 Correct 337 ms 141320 KB Output is correct
96 Correct 379 ms 141916 KB Output is correct
97 Correct 2288 ms 173124 KB Output is correct
98 Correct 439 ms 134356 KB Output is correct
99 Correct 404 ms 142212 KB Output is correct
100 Correct 375 ms 140872 KB Output is correct
101 Correct 615 ms 144856 KB Output is correct
102 Correct 403 ms 141492 KB Output is correct
103 Execution timed out 3087 ms 187124 KB Time limit exceeded
104 Halted 0 ms 0 KB -