oj.uz

Submission #854708

# Submission time Handle Problem Language Result Execution time Memory
854708 2023-09-28T15:22:55 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 780708 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][25];
pii UR[303030][25];
int V[303030][50];
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;
	}

	int left(int x) {
		x = min(x, n - 1);
		return x < 0 ? -1 : l[lc[x]];
	}
	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 = lb + 1; i <= x; i++) rc[i] = c;
			r[c] = x;
			for (int i = max(0, lb); i < x; i++) lc[i] = c;
			l[c] = lb; l[lc[x]] = x;
		} else {
			for (int i = x + 1; i <= min(n - 1, rb); i++) rc[i] = c;
			r[c] = rb;
			r[rc[x]] = x;
			for (int i = x; i < rb; i++) lc[i] = c;
			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:148: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]
  148 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:166: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]
  166 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:223:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  223 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:223:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  223 |  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 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12740 KB Output is correct
4 Correct 2 ms 12636 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 12892 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 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12872 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12864 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13804 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 21644 KB Output is correct
20 Correct 15 ms 21340 KB Output is correct
21 Correct 16 ms 21340 KB Output is correct
22 Correct 15 ms 20380 KB Output is correct
23 Correct 19 ms 20868 KB Output is correct
24 Correct 13 ms 20176 KB Output is correct
25 Correct 12 ms 19804 KB Output is correct
26 Correct 13 ms 20316 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2092 ms 773592 KB Output is correct
2 Correct 2132 ms 780472 KB Output is correct
3 Correct 2127 ms 780708 KB Output is correct
4 Correct 2047 ms 779828 KB Output is correct
5 Correct 1342 ms 464640 KB Output is correct
6 Correct 1257 ms 667264 KB Output is correct
7 Correct 1550 ms 684924 KB Output is correct
8 Correct 1422 ms 679876 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 618 ms 201192 KB Output is correct
3 Correct 2290 ms 685736 KB Output is correct
4 Correct 2278 ms 685192 KB Output is correct
5 Correct 2620 ms 691840 KB Output is correct
6 Correct 1128 ms 364032 KB Output is correct
7 Correct 451 ms 187076 KB Output is correct
8 Correct 56 ms 48580 KB Output is correct
9 Correct 2413 ms 696932 KB Output is correct
10 Execution timed out 3035 ms 715352 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1740 ms 678808 KB Output is correct
2 Correct 999 ms 648324 KB Output is correct
3 Correct 2965 ms 741336 KB Output is correct
4 Correct 1126 ms 659968 KB Output is correct
5 Correct 1059 ms 656160 KB Output is correct
6 Correct 2836 ms 764348 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12740 KB Output is correct
4 Correct 2 ms 12636 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 12892 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 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12872 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12864 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13804 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 21644 KB Output is correct
20 Correct 15 ms 21340 KB Output is correct
21 Correct 16 ms 21340 KB Output is correct
22 Correct 15 ms 20380 KB Output is correct
23 Correct 19 ms 20868 KB Output is correct
24 Correct 13 ms 20176 KB Output is correct
25 Correct 12 ms 19804 KB Output is correct
26 Correct 13 ms 20316 KB Output is correct
27 Correct 34 ms 34132 KB Output is correct
28 Correct 38 ms 34524 KB Output is correct
29 Correct 34 ms 34128 KB Output is correct
30 Correct 34 ms 32348 KB Output is correct
31 Correct 28 ms 31832 KB Output is correct
32 Correct 31 ms 31824 KB Output is correct
33 Correct 492 ms 224896 KB Output is correct
34 Correct 554 ms 226084 KB Output is correct
35 Correct 592 ms 226888 KB Output is correct
36 Correct 424 ms 194940 KB Output is correct
37 Correct 436 ms 195488 KB Output is correct
38 Correct 472 ms 197296 KB Output is correct
39 Correct 172 ms 77656 KB Output is correct
40 Correct 160 ms 77508 KB Output is correct
41 Correct 157 ms 77552 KB Output is correct
42 Correct 212 ms 82112 KB Output is correct
43 Correct 272 ms 189376 KB Output is correct
44 Correct 265 ms 188324 KB Output is correct
45 Correct 266 ms 189380 KB Output is correct
46 Correct 269 ms 189140 KB Output is correct
47 Correct 272 ms 187896 KB Output is correct
48 Correct 265 ms 189200 KB Output is correct
49 Correct 269 ms 187072 KB Output is correct
50 Correct 264 ms 188396 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12740 KB Output is correct
4 Correct 2 ms 12636 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 12892 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 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12872 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12864 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13804 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 21644 KB Output is correct
20 Correct 15 ms 21340 KB Output is correct
21 Correct 16 ms 21340 KB Output is correct
22 Correct 15 ms 20380 KB Output is correct
23 Correct 19 ms 20868 KB Output is correct
24 Correct 13 ms 20176 KB Output is correct
25 Correct 12 ms 19804 KB Output is correct
26 Correct 13 ms 20316 KB Output is correct
27 Correct 2092 ms 773592 KB Output is correct
28 Correct 2132 ms 780472 KB Output is correct
29 Correct 2127 ms 780708 KB Output is correct
30 Correct 2047 ms 779828 KB Output is correct
31 Correct 1342 ms 464640 KB Output is correct
32 Correct 1257 ms 667264 KB Output is correct
33 Correct 1550 ms 684924 KB Output is correct
34 Correct 1422 ms 679876 KB Output is correct
35 Correct 1 ms 12636 KB Output is correct
36 Correct 618 ms 201192 KB Output is correct
37 Correct 2290 ms 685736 KB Output is correct
38 Correct 2278 ms 685192 KB Output is correct
39 Correct 2620 ms 691840 KB Output is correct
40 Correct 1128 ms 364032 KB Output is correct
41 Correct 451 ms 187076 KB Output is correct
42 Correct 56 ms 48580 KB Output is correct
43 Correct 2413 ms 696932 KB Output is correct
44 Execution timed out 3035 ms 715352 KB Time limit exceeded
45 Halted 0 ms 0 KB -