oj.uz

Submission #854737

# Submission time Handle Problem Language Result Execution time Memory
854737 2023-09-28T17:15:09 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 715984 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;
	bool fg;

	void set(int _n) {
		n = _n;
		fg = false;
	}

	void init() {
		l.resize(n + 1); r.resize(n + 1);
		c.resize(n); chk.resize(n);
		cid = 0;
		l[0] = -1; r[0] = n;
	}

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

	void upd(int x) {
		if (!fg) { fg = true; init(); }
		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 && !chk[x + 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 && !chk[x - 1]) 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.set(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:159: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]
  159 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:177: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]
  177 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:234:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  234 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:234:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  234 |  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 12636 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12900 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 13144 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 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 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 14028 KB Output is correct
18 Correct 4 ms 13912 KB Output is correct
19 Correct 14 ms 22684 KB Output is correct
20 Correct 16 ms 22872 KB Output is correct
21 Correct 17 ms 22876 KB Output is correct
22 Correct 13 ms 21852 KB Output is correct
23 Correct 19 ms 22368 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 12 ms 21596 KB Output is correct
26 Correct 12 ms 21924 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2399 ms 713100 KB Output is correct
2 Correct 2456 ms 715984 KB Output is correct
3 Correct 2421 ms 714352 KB Output is correct
4 Correct 2386 ms 713000 KB Output is correct
5 Correct 1463 ms 424852 KB Output is correct
6 Correct 1392 ms 616340 KB Output is correct
7 Correct 1669 ms 626592 KB Output is correct
8 Correct 1549 ms 624956 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 671 ms 197180 KB Output is correct
3 Correct 2288 ms 640508 KB Output is correct
4 Correct 2220 ms 640216 KB Output is correct
5 Correct 2652 ms 647108 KB Output is correct
6 Correct 1173 ms 338536 KB Output is correct
7 Correct 470 ms 178528 KB Output is correct
8 Correct 54 ms 48320 KB Output is correct
9 Correct 2356 ms 643348 KB Output is correct
10 Execution timed out 3069 ms 660156 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 634068 KB Output is correct
2 Correct 1083 ms 602496 KB Output is correct
3 Execution timed out 3046 ms 687748 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 12636 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12900 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 13144 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 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 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 14028 KB Output is correct
18 Correct 4 ms 13912 KB Output is correct
19 Correct 14 ms 22684 KB Output is correct
20 Correct 16 ms 22872 KB Output is correct
21 Correct 17 ms 22876 KB Output is correct
22 Correct 13 ms 21852 KB Output is correct
23 Correct 19 ms 22368 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 12 ms 21596 KB Output is correct
26 Correct 12 ms 21924 KB Output is correct
27 Correct 32 ms 33116 KB Output is correct
28 Correct 33 ms 33284 KB Output is correct
29 Correct 33 ms 33272 KB Output is correct
30 Correct 37 ms 31828 KB Output is correct
31 Correct 26 ms 31060 KB Output is correct
32 Correct 30 ms 31068 KB Output is correct
33 Correct 604 ms 215700 KB Output is correct
34 Correct 621 ms 217128 KB Output is correct
35 Correct 689 ms 218932 KB Output is correct
36 Correct 458 ms 190912 KB Output is correct
37 Correct 475 ms 191480 KB Output is correct
38 Correct 513 ms 193432 KB Output is correct
39 Correct 186 ms 72184 KB Output is correct
40 Correct 161 ms 72288 KB Output is correct
41 Correct 169 ms 72396 KB Output is correct
42 Correct 194 ms 76224 KB Output is correct
43 Correct 302 ms 185544 KB Output is correct
44 Correct 336 ms 184116 KB Output is correct
45 Correct 307 ms 185384 KB Output is correct
46 Correct 310 ms 185216 KB Output is correct
47 Correct 326 ms 183764 KB Output is correct
48 Correct 315 ms 185212 KB Output is correct
49 Correct 296 ms 183012 KB Output is correct
50 Correct 310 ms 184572 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 12636 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12900 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 13144 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 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 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 14028 KB Output is correct
18 Correct 4 ms 13912 KB Output is correct
19 Correct 14 ms 22684 KB Output is correct
20 Correct 16 ms 22872 KB Output is correct
21 Correct 17 ms 22876 KB Output is correct
22 Correct 13 ms 21852 KB Output is correct
23 Correct 19 ms 22368 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 12 ms 21596 KB Output is correct
26 Correct 12 ms 21924 KB Output is correct
27 Correct 2399 ms 713100 KB Output is correct
28 Correct 2456 ms 715984 KB Output is correct
29 Correct 2421 ms 714352 KB Output is correct
30 Correct 2386 ms 713000 KB Output is correct
31 Correct 1463 ms 424852 KB Output is correct
32 Correct 1392 ms 616340 KB Output is correct
33 Correct 1669 ms 626592 KB Output is correct
34 Correct 1549 ms 624956 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 671 ms 197180 KB Output is correct
37 Correct 2288 ms 640508 KB Output is correct
38 Correct 2220 ms 640216 KB Output is correct
39 Correct 2652 ms 647108 KB Output is correct
40 Correct 1173 ms 338536 KB Output is correct
41 Correct 470 ms 178528 KB Output is correct
42 Correct 54 ms 48320 KB Output is correct
43 Correct 2356 ms 643348 KB Output is correct
44 Execution timed out 3069 ms 660156 KB Time limit exceeded
45 Halted 0 ms 0 KB -