oj.uz

Submission #851260

# Submission time Handle Problem Language Result Execution time Memory
851260 2023-09-19T08:12:18 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
87 / 100
 2025 ms 185812 KB 
#include <bits/stdc++.h>

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

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

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;
}

void chk(int cand) {
	if (intersect(cur, cand)) {
		int &t = ans[cur];
		if (pii(R[cand], -cand) > pii(R[t], -t)) 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) {
		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);
			it++;
		}
		it = tmp;
		for (int i = 0; i < K; i++) {
			if (it == T[idx].s.begin()) break;
			it--;
			chk(it->second);
		}
	}

	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) {
		p += base; p--;
		while (p >= 1) {
			chk_node(p, y);
			p >>= 1;
		}
	}
};

int main() {
	scanf("%d", &N);
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d", &X[i], &Y[i], &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] + R[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:111:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  111 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:111:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  111 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~
circle_selection.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d%d", &X[i], &Y[i], &R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 6600 KB Output is correct
3 Correct 1 ms 6488 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 6492 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 2 ms 6500 KB Output is correct
10 Correct 1 ms 6488 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 6488 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6488 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 6744 KB Output is correct
19 Correct 5 ms 8280 KB Output is correct
20 Correct 5 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 6 ms 8792 KB Output is correct
23 Correct 10 ms 9560 KB Output is correct
24 Correct 7 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 6 ms 8792 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 116660 KB Output is correct
2 Correct 397 ms 115380 KB Output is correct
3 Correct 413 ms 116200 KB Output is correct
4 Correct 400 ms 116448 KB Output is correct
5 Correct 335 ms 67512 KB Output is correct
6 Correct 429 ms 125112 KB Output is correct
7 Correct 413 ms 117584 KB Output is correct
8 Correct 428 ms 119796 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 284 ms 56772 KB Output is correct
3 Correct 1115 ms 182380 KB Output is correct
4 Correct 1087 ms 181840 KB Output is correct
5 Correct 1533 ms 179116 KB Output is correct
6 Correct 472 ms 84092 KB Output is correct
7 Correct 148 ms 43640 KB Output is correct
8 Correct 20 ms 14552 KB Output is correct
9 Correct 1219 ms 185812 KB Output is correct
10 Correct 2025 ms 174700 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 173436 KB Output is correct
2 Correct 351 ms 136884 KB Output is correct
3 Correct 888 ms 124168 KB Output is correct
4 Correct 388 ms 141344 KB Output is correct
5 Correct 363 ms 138360 KB Output is correct
6 Correct 637 ms 117200 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 6600 KB Output is correct
3 Correct 1 ms 6488 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 6492 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 2 ms 6500 KB Output is correct
10 Correct 1 ms 6488 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 6488 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6488 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 6744 KB Output is correct
19 Correct 5 ms 8280 KB Output is correct
20 Correct 5 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 6 ms 8792 KB Output is correct
23 Correct 10 ms 9560 KB Output is correct
24 Correct 7 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 6 ms 8792 KB Output is correct
27 Correct 9 ms 10072 KB Output is correct
28 Correct 9 ms 10072 KB Output is correct
29 Correct 9 ms 10072 KB Output is correct
30 Correct 17 ms 11864 KB Output is correct
31 Correct 12 ms 11096 KB Output is correct
32 Correct 11 ms 11096 KB Output is correct
33 Correct 103 ms 34896 KB Output is correct
34 Correct 103 ms 34896 KB Output is correct
35 Correct 110 ms 34896 KB Output is correct
36 Correct 177 ms 47296 KB Output is correct
37 Correct 156 ms 47888 KB Output is correct
38 Correct 171 ms 50060 KB Output is correct
39 Correct 139 ms 12340 KB Output is correct
40 Correct 136 ms 12228 KB Output is correct
41 Correct 140 ms 12328 KB Output is correct
42 Correct 146 ms 12712 KB Output is correct
43 Correct 103 ms 41408 KB Output is correct
44 Correct 106 ms 40892 KB Output is correct
45 Correct 102 ms 41288 KB Output is correct
46 Correct 111 ms 41412 KB Output is correct
47 Correct 102 ms 40384 KB Output is correct
48 Correct 112 ms 41412 KB Output is correct
49 Correct 99 ms 40132 KB Output is correct
50 Correct 106 ms 40896 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 6600 KB Output is correct
3 Correct 1 ms 6488 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 6492 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 2 ms 6500 KB Output is correct
10 Correct 1 ms 6488 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 6488 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 6488 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 6744 KB Output is correct
19 Correct 5 ms 8280 KB Output is correct
20 Correct 5 ms 8280 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 6 ms 8792 KB Output is correct
23 Correct 10 ms 9560 KB Output is correct
24 Correct 7 ms 8792 KB Output is correct
25 Correct 5 ms 8536 KB Output is correct
26 Correct 6 ms 8792 KB Output is correct
27 Correct 417 ms 116660 KB Output is correct
28 Correct 397 ms 115380 KB Output is correct
29 Correct 413 ms 116200 KB Output is correct
30 Correct 400 ms 116448 KB Output is correct
31 Correct 335 ms 67512 KB Output is correct
32 Correct 429 ms 125112 KB Output is correct
33 Correct 413 ms 117584 KB Output is correct
34 Correct 428 ms 119796 KB Output is correct
35 Correct 1 ms 6488 KB Output is correct
36 Correct 284 ms 56772 KB Output is correct
37 Correct 1115 ms 182380 KB Output is correct
38 Correct 1087 ms 181840 KB Output is correct
39 Correct 1533 ms 179116 KB Output is correct
40 Correct 472 ms 84092 KB Output is correct
41 Correct 148 ms 43640 KB Output is correct
42 Correct 20 ms 14552 KB Output is correct
43 Correct 1219 ms 185812 KB Output is correct
44 Correct 2025 ms 174700 KB Output is correct
45 Correct 759 ms 173436 KB Output is correct
46 Correct 351 ms 136884 KB Output is correct
47 Correct 888 ms 124168 KB Output is correct
48 Correct 388 ms 141344 KB Output is correct
49 Correct 363 ms 138360 KB Output is correct
50 Correct 637 ms 117200 KB Output is correct
51 Correct 9 ms 10072 KB Output is correct
52 Correct 9 ms 10072 KB Output is correct
53 Correct 9 ms 10072 KB Output is correct
54 Correct 17 ms 11864 KB Output is correct
55 Correct 12 ms 11096 KB Output is correct
56 Correct 11 ms 11096 KB Output is correct
57 Correct 103 ms 34896 KB Output is correct
58 Correct 103 ms 34896 KB Output is correct
59 Correct 110 ms 34896 KB Output is correct
60 Correct 177 ms 47296 KB Output is correct
61 Correct 156 ms 47888 KB Output is correct
62 Correct 171 ms 50060 KB Output is correct
63 Correct 139 ms 12340 KB Output is correct
64 Correct 136 ms 12228 KB Output is correct
65 Correct 140 ms 12328 KB Output is correct
66 Correct 146 ms 12712 KB Output is correct
67 Correct 103 ms 41408 KB Output is correct
68 Correct 106 ms 40892 KB Output is correct
69 Correct 102 ms 41288 KB Output is correct
70 Correct 111 ms 41412 KB Output is correct
71 Correct 102 ms 40384 KB Output is correct
72 Correct 112 ms 41412 KB Output is correct
73 Correct 99 ms 40132 KB Output is correct
74 Correct 106 ms 40896 KB Output is correct
75 Correct 420 ms 112736 KB Output is correct
76 Correct 409 ms 111744 KB Output is correct
77 Correct 389 ms 112964 KB Output is correct
78 Correct 430 ms 111540 KB Output is correct
79 Incorrect 500 ms 113516 KB Output isn't correct
80 Halted 0 ms 0 KB -