oj.uz

Submission #854714

# Submission time Handle Problem Language Result Execution time Memory
854714 2023-09-28T15:31:53 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 754112 KB 
#include <bits/stdc++.h>

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

const int K = 3;

int N;
int X[303030];
int Y[303030];
int R[303030];
int XL[303030];
int XR[303030];
pii UL[303030][22];
pii UR[303030][22];
int V[303030][44];
int ulp[303030];
int urp[303030];
int vp[303030];
int ans[303030];
char rr;

struct DSU {
	int n;
	vector<int> l, r, lc, rc;
	int c;

	DSU(int _n = 0) : n(_n), l(_n + 1), r(_n + 1), lc(_n), rc(_n), c(0) {
		l[0] = -1; r[0] = n;
	}

	inline int left(int x) {
		x = min(x, n - 1);
		return x < 0 ? -1 : l[lc[x]];
	}
	inline int right(int x) {
		x = max(x, 0);
		return x >= n ? n : r[rc[x]];
	}

	void upd(int x) {
		int lb = left(x), rb = right(x);
		c++;
		if (x - lb <= rb - x) {
			for (int i = max(0, lb); i <= x; i++) {
				if (i >= lb + 1) rc[i] = c;
				if (i < x) lc[i] = c;
			}
			l[c] = lb; l[lc[x]] = x;
			r[c] = x;
		} else {
			for (int i = x; i <= min(n - 1, rb); i++) {
				if (i < rb) lc[i] = c;
				if (i > x) rc[i] = c;
			}
			r[c] = rb; r[rc[x]] = x;
			l[c] = x;
		}
	}
};

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) {
	int dx = X[i] - X[j], dy = Y[i] - Y[j], r = R[i] + R[j];
	return (long long)dx * dx + (long long)dy * dy <= (long long)r * r;
}

inline void upd_ans(int cur, int cand) {
	int &t = ans[cur];
	if (R[t] > R[cand] || (R[t] == R[cand] && t < cand)) return;
	if (intersect(cur, cand)) t = cand;
}

struct SegTree {
	struct Node {
		vector<pii> v;
		DSU uf;
	};

	int n, base;
	vector<Node> T;

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

	void add_line(int p, int q, int y, int i) {
		p += base; q += base;
		p--; q--;
		while (p <= q) {
			if (p & 1) {
				V[i][vp[i]++] = T[p].v.size();
				T[p].v.emplace_back(y, i);
				p++;
			}
			if (~q & 1) {
				V[i][vp[i]++] = T[q].v.size();
				T[q].v.emplace_back(y, i);
				q--;
			}
			p >>= 1; q >>= 1;
		}
	}

	void add_point(int p, int i, bool is_left) {
		p += base; p--;
		while (p) {
			if (is_left) UL[i][ulp[i]++] = {p, (int)T[p].v.size()};
			else UR[i][urp[i]++] = {p, (int)T[p].v.size()};
			p >>= 1;
		}
	}

	void init() {
		for (int i = 1; i < base + base; i++) T[i].uf = DSU(T[i].v.size());
	}

	void upd(int p, int q, int i) {
		p += base; q += base;
		p--; q--;
		int ptr = 0;
		while (p <= q) {
			if (p & 1) {
				T[p].uf.upd(V[i][ptr++]);
				p++;
			}
			if (~q & 1) {
				T[q].uf.upd(V[i][ptr++]);
				q--;
			}
			p >>= 1; q >>= 1;
		}
	}

	void chk(int cur, bool is_left) {
		if (is_left) {
			for (int i = 0; i < ulp[cur]; i++) {
				int p, s; tie(p, s) = UL[cur][i];
				int t = s;
				for (int j = 0; j < K; j++) {
					t = T[p].uf.right(t);
					if (t >= T[p].v.size()) break;
					upd_ans(cur, T[p].v[t].second);
					t++;
				}
				t = s;
				for (int j = 0; j < K; j++) {
					t = T[p].uf.left(t);
					if (t < 0) break;
					upd_ans(cur, T[p].v[t].second);
					t--;
				}
			}
		} else {
			for (int i = 0; i < urp[cur]; i++) {
				int p, s; tie(p, s) = UR[cur][i];
				int t = s;
				for (int j = 0; j < K; j++) {
					t = T[p].uf.right(t);
					if (t >= T[p].v.size()) break;
					upd_ans(cur, T[p].v[t].second);
					t++;
				}
				t = s;
				for (int j = 0; j < K; j++) {
					t = T[p].uf.left(t);
					if (t < 0) break;
					upd_ans(cur, T[p].v[t].second);
					t--;
				}
			}
		}
	}
};

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> ord(N);
	iota(ord.begin(), ord.end(), 1);

	sort(ord.begin(), ord.end(), [&](int a, int b) { return Y[a] < Y[b]; });
	for (int i : ord) {
		seg.add_line(XL[i], XR[i], Y[i], i);
		seg.add_point(XL[i], i, true);
		seg.add_point(XR[i], i, false);
	}
	seg.init();

	sort(ord.begin(), ord.end(), [&](int a, int b) {
		if (R[a] == R[b]) return a < b;
		return R[a] > R[b];
	});
	for (int i : ord) {
		ans[i] = i;
		seg.chk(i, true);
		seg.chk(i, false);
		if (ans[i] == i) seg.upd(XL[i], XR[i], i);
	}

	for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
	return 0;
}

Compilation message

circle_selection.cpp: In member function 'void SegTree::chk(int, bool)':
circle_selection.cpp:151:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:169:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:226:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  226 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:226:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  226 |  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 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 3 ms 13840 KB Output is correct
19 Correct 15 ms 23132 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 22 ms 23348 KB Output is correct
22 Correct 16 ms 22260 KB Output is correct
23 Correct 22 ms 22780 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 12 ms 21728 KB Output is correct
26 Correct 13 ms 22108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 751984 KB Output is correct
2 Correct 2219 ms 752840 KB Output is correct
3 Correct 2239 ms 754112 KB Output is correct
4 Correct 2116 ms 752584 KB Output is correct
5 Correct 1353 ms 438704 KB Output is correct
6 Correct 1250 ms 640904 KB Output is correct
7 Correct 1545 ms 659692 KB Output is correct
8 Correct 1454 ms 654016 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 627 ms 196748 KB Output is correct
3 Correct 2263 ms 662840 KB Output is correct
4 Correct 2359 ms 662652 KB Output is correct
5 Execution timed out 3069 ms 672680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 657412 KB Output is correct
2 Correct 1125 ms 626608 KB Output is correct
3 Execution timed out 3050 ms 719196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 3 ms 13840 KB Output is correct
19 Correct 15 ms 23132 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 22 ms 23348 KB Output is correct
22 Correct 16 ms 22260 KB Output is correct
23 Correct 22 ms 22780 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 12 ms 21728 KB Output is correct
26 Correct 13 ms 22108 KB Output is correct
27 Correct 33 ms 34136 KB Output is correct
28 Correct 36 ms 34140 KB Output is correct
29 Correct 36 ms 34132 KB Output is correct
30 Correct 34 ms 32444 KB Output is correct
31 Correct 30 ms 31748 KB Output is correct
32 Correct 28 ms 31772 KB Output is correct
33 Correct 503 ms 220304 KB Output is correct
34 Correct 557 ms 221376 KB Output is correct
35 Correct 609 ms 222404 KB Output is correct
36 Correct 422 ms 190636 KB Output is correct
37 Correct 434 ms 191100 KB Output is correct
38 Correct 484 ms 192964 KB Output is correct
39 Correct 160 ms 73160 KB Output is correct
40 Correct 157 ms 73152 KB Output is correct
41 Correct 158 ms 73156 KB Output is correct
42 Correct 201 ms 77680 KB Output is correct
43 Correct 266 ms 185032 KB Output is correct
44 Correct 273 ms 183996 KB Output is correct
45 Correct 266 ms 184760 KB Output is correct
46 Correct 271 ms 184840 KB Output is correct
47 Correct 268 ms 183236 KB Output is correct
48 Correct 265 ms 184728 KB Output is correct
49 Correct 277 ms 182732 KB Output is correct
50 Correct 266 ms 183840 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12888 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 3 ms 13840 KB Output is correct
19 Correct 15 ms 23132 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 22 ms 23348 KB Output is correct
22 Correct 16 ms 22260 KB Output is correct
23 Correct 22 ms 22780 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 12 ms 21728 KB Output is correct
26 Correct 13 ms 22108 KB Output is correct
27 Correct 2154 ms 751984 KB Output is correct
28 Correct 2219 ms 752840 KB Output is correct
29 Correct 2239 ms 754112 KB Output is correct
30 Correct 2116 ms 752584 KB Output is correct
31 Correct 1353 ms 438704 KB Output is correct
32 Correct 1250 ms 640904 KB Output is correct
33 Correct 1545 ms 659692 KB Output is correct
34 Correct 1454 ms 654016 KB Output is correct
35 Correct 2 ms 12632 KB Output is correct
36 Correct 627 ms 196748 KB Output is correct
37 Correct 2263 ms 662840 KB Output is correct
38 Correct 2359 ms 662652 KB Output is correct
39 Execution timed out 3069 ms 672680 KB Time limit exceeded
40 Halted 0 ms 0 KB -