oj.uz

답안 #851997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851997 2023-09-21T04:46:31 Z dlalswp25 원 고르기 (APIO18_circle_selection) C++17
64 / 100
 1471 ms 195416 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});
		if (it != T[idx].s.end()) chk(it->second);
		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:119:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  119 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:119:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  119 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 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 6488 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 6744 KB Output is correct
17 Correct 2 ms 6744 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 8536 KB Output is correct
21 Correct 5 ms 8536 KB Output is correct
22 Correct 7 ms 9048 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 125364 KB Output is correct
2 Correct 366 ms 125108 KB Output is correct
3 Correct 364 ms 125148 KB Output is correct
4 Correct 356 ms 123756 KB Output is correct
5 Correct 321 ms 71788 KB Output is correct
6 Correct 347 ms 133556 KB Output is correct
7 Correct 337 ms 125364 KB Output is correct
8 Correct 346 ms 127588 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 237 ms 59588 KB Output is correct
3 Correct 924 ms 191600 KB Output is correct
4 Correct 906 ms 192276 KB Output is correct
5 Correct 1143 ms 189120 KB Output is correct
6 Correct 386 ms 89532 KB Output is correct
7 Correct 129 ms 46312 KB Output is correct
8 Correct 15 ms 15052 KB Output is correct
9 Correct 1076 ms 195416 KB Output is correct
10 Correct 1471 ms 185500 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 650 ms 182012 KB Output is correct
2 Correct 305 ms 147892 KB Output is correct
3 Incorrect 617 ms 134260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 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 6488 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 6744 KB Output is correct
17 Correct 2 ms 6744 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 8536 KB Output is correct
21 Correct 5 ms 8536 KB Output is correct
22 Correct 7 ms 9048 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct
27 Correct 8 ms 10328 KB Output is correct
28 Correct 8 ms 10328 KB Output is correct
29 Correct 8 ms 10328 KB Output is correct
30 Correct 13 ms 12120 KB Output is correct
31 Correct 9 ms 11352 KB Output is correct
32 Correct 10 ms 11352 KB Output is correct
33 Correct 91 ms 37832 KB Output is correct
34 Correct 110 ms 38056 KB Output is correct
35 Correct 100 ms 37708 KB Output is correct
36 Correct 152 ms 50248 KB Output is correct
37 Correct 153 ms 50628 KB Output is correct
38 Correct 180 ms 52676 KB Output is correct
39 Correct 103 ms 12692 KB Output is correct
40 Correct 102 ms 12704 KB Output is correct
41 Correct 103 ms 12552 KB Output is correct
42 Correct 111 ms 13252 KB Output is correct
43 Correct 91 ms 44224 KB Output is correct
44 Correct 88 ms 43596 KB Output is correct
45 Correct 91 ms 44368 KB Output is correct
46 Correct 94 ms 44108 KB Output is correct
47 Correct 89 ms 43204 KB Output is correct
48 Correct 91 ms 44112 KB Output is correct
49 Correct 88 ms 43200 KB Output is correct
50 Correct 90 ms 43628 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6488 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 6488 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 6744 KB Output is correct
17 Correct 2 ms 6744 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 8536 KB Output is correct
21 Correct 5 ms 8536 KB Output is correct
22 Correct 7 ms 9048 KB Output is correct
23 Correct 9 ms 9564 KB Output is correct
24 Correct 6 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 5 ms 8792 KB Output is correct
27 Correct 380 ms 125364 KB Output is correct
28 Correct 366 ms 125108 KB Output is correct
29 Correct 364 ms 125148 KB Output is correct
30 Correct 356 ms 123756 KB Output is correct
31 Correct 321 ms 71788 KB Output is correct
32 Correct 347 ms 133556 KB Output is correct
33 Correct 337 ms 125364 KB Output is correct
34 Correct 346 ms 127588 KB Output is correct
35 Correct 1 ms 6488 KB Output is correct
36 Correct 237 ms 59588 KB Output is correct
37 Correct 924 ms 191600 KB Output is correct
38 Correct 906 ms 192276 KB Output is correct
39 Correct 1143 ms 189120 KB Output is correct
40 Correct 386 ms 89532 KB Output is correct
41 Correct 129 ms 46312 KB Output is correct
42 Correct 15 ms 15052 KB Output is correct
43 Correct 1076 ms 195416 KB Output is correct
44 Correct 1471 ms 185500 KB Output is correct
45 Correct 650 ms 182012 KB Output is correct
46 Correct 305 ms 147892 KB Output is correct
47 Incorrect 617 ms 134260 KB Output isn't correct
48 Halted 0 ms 0 KB -