oj.uz

Submission #854720

# Submission time Handle Problem Language Result Execution time Memory
854720 2023-09-28T15:41:20 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
19 / 100
 2942 ms 771768 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, c;
	vector<bool> chk;
	int cid;

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

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

	void upd(int x) {
		int lb = left(x), rb = right(x);
		chk[x] = true;
		cid++;
		if (x - lb <= rb - x) {
			for (int i = lb + 1; i < x; i++) c[i] = cid;
			l[cid] = lb; r[cid] = x;
			if (x < n - 1) l[c[x + 1]] = x;
		} else {
			for (int i = x + 1; i < rb; i++) c[i] = cid;
			l[cid] = x; r[cid] = rb;
			if (x) r[c[x - 1]] = 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:147: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]
  147 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:165: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]
  165 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:222:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  222 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:222:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  222 |  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 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 1 ms 12784 KB Output is correct
6 Correct 3 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 12916 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 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 23644 KB Output is correct
20 Correct 15 ms 23644 KB Output is correct
21 Correct 17 ms 23644 KB Output is correct
22 Correct 13 ms 22620 KB Output is correct
23 Correct 18 ms 23128 KB Output is correct
24 Correct 13 ms 22620 KB Output is correct
25 Correct 13 ms 22372 KB Output is correct
26 Correct 14 ms 22512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2111 ms 770328 KB Output is correct
2 Correct 2205 ms 771768 KB Output is correct
3 Correct 2204 ms 770704 KB Output is correct
4 Correct 2109 ms 769856 KB Output is correct
5 Correct 1375 ms 453708 KB Output is correct
6 Correct 1277 ms 673928 KB Output is correct
7 Correct 1623 ms 692340 KB Output is correct
8 Correct 1484 ms 686208 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Incorrect 576 ms 204836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1677 ms 691308 KB Output is correct
2 Correct 1030 ms 660512 KB Output is correct
3 Incorrect 2942 ms 744208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 1 ms 12784 KB Output is correct
6 Correct 3 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 12916 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 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 23644 KB Output is correct
20 Correct 15 ms 23644 KB Output is correct
21 Correct 17 ms 23644 KB Output is correct
22 Correct 13 ms 22620 KB Output is correct
23 Correct 18 ms 23128 KB Output is correct
24 Correct 13 ms 22620 KB Output is correct
25 Correct 13 ms 22372 KB Output is correct
26 Correct 14 ms 22512 KB Output is correct
27 Correct 35 ms 34900 KB Output is correct
28 Correct 37 ms 35008 KB Output is correct
29 Correct 36 ms 34972 KB Output is correct
30 Correct 35 ms 33372 KB Output is correct
31 Correct 28 ms 33112 KB Output is correct
32 Correct 28 ms 32604 KB Output is correct
33 Correct 506 ms 223680 KB Output is correct
34 Correct 544 ms 224964 KB Output is correct
35 Correct 614 ms 226420 KB Output is correct
36 Correct 433 ms 198852 KB Output is correct
37 Correct 422 ms 199208 KB Output is correct
38 Correct 460 ms 201156 KB Output is correct
39 Incorrect 156 ms 72384 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 1 ms 12784 KB Output is correct
6 Correct 3 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 12916 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 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 4 ms 13916 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 16 ms 23644 KB Output is correct
20 Correct 15 ms 23644 KB Output is correct
21 Correct 17 ms 23644 KB Output is correct
22 Correct 13 ms 22620 KB Output is correct
23 Correct 18 ms 23128 KB Output is correct
24 Correct 13 ms 22620 KB Output is correct
25 Correct 13 ms 22372 KB Output is correct
26 Correct 14 ms 22512 KB Output is correct
27 Correct 2111 ms 770328 KB Output is correct
28 Correct 2205 ms 771768 KB Output is correct
29 Correct 2204 ms 770704 KB Output is correct
30 Correct 2109 ms 769856 KB Output is correct
31 Correct 1375 ms 453708 KB Output is correct
32 Correct 1277 ms 673928 KB Output is correct
33 Correct 1623 ms 692340 KB Output is correct
34 Correct 1484 ms 686208 KB Output is correct
35 Correct 1 ms 12632 KB Output is correct
36 Incorrect 576 ms 204836 KB Output isn't correct
37 Halted 0 ms 0 KB -