oj.uz

Submission #854712

# Submission time Handle Problem Language Result Execution time Memory
854712 2023-09-28T15:27:27 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 753140 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 = 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:150: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]
  150 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:168: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]
  168 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:225:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  225 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:225:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  225 |  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 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 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 13128 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 4 ms 13912 KB Output is correct
17 Correct 4 ms 13912 KB Output is correct
18 Correct 4 ms 13860 KB Output is correct
19 Correct 18 ms 23204 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 18 ms 23132 KB Output is correct
22 Correct 16 ms 22108 KB Output is correct
23 Correct 18 ms 22620 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 13 ms 21852 KB Output is correct
26 Correct 15 ms 22032 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 752504 KB Output is correct
2 Correct 2238 ms 751748 KB Output is correct
3 Correct 2289 ms 753140 KB Output is correct
4 Correct 2145 ms 751612 KB Output is correct
5 Correct 1375 ms 439480 KB Output is correct
6 Correct 1315 ms 641620 KB Output is correct
7 Correct 1601 ms 660216 KB Output is correct
8 Correct 1507 ms 653396 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 641 ms 196656 KB Output is correct
3 Correct 2410 ms 663088 KB Output is correct
4 Correct 2356 ms 664340 KB Output is correct
5 Correct 2793 ms 672624 KB Output is correct
6 Correct 1193 ms 349000 KB Output is correct
7 Correct 539 ms 182704 KB Output is correct
8 Correct 62 ms 50292 KB Output is correct
9 Correct 2444 ms 666696 KB Output is correct
10 Execution timed out 3044 ms 685968 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1776 ms 658576 KB Output is correct
2 Correct 1043 ms 626612 KB Output is correct
3 Execution timed out 3017 ms 720356 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 12636 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 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 13128 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 4 ms 13912 KB Output is correct
17 Correct 4 ms 13912 KB Output is correct
18 Correct 4 ms 13860 KB Output is correct
19 Correct 18 ms 23204 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 18 ms 23132 KB Output is correct
22 Correct 16 ms 22108 KB Output is correct
23 Correct 18 ms 22620 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 13 ms 21852 KB Output is correct
26 Correct 15 ms 22032 KB Output is correct
27 Correct 38 ms 34200 KB Output is correct
28 Correct 37 ms 34272 KB Output is correct
29 Correct 38 ms 34304 KB Output is correct
30 Correct 40 ms 32348 KB Output is correct
31 Correct 29 ms 31836 KB Output is correct
32 Correct 30 ms 31580 KB Output is correct
33 Correct 511 ms 220356 KB Output is correct
34 Correct 558 ms 221424 KB Output is correct
35 Correct 667 ms 222700 KB Output is correct
36 Correct 468 ms 190744 KB Output is correct
37 Correct 450 ms 191128 KB Output is correct
38 Correct 495 ms 192908 KB Output is correct
39 Correct 166 ms 72984 KB Output is correct
40 Correct 173 ms 73356 KB Output is correct
41 Correct 161 ms 73128 KB Output is correct
42 Correct 197 ms 77564 KB Output is correct
43 Correct 283 ms 184956 KB Output is correct
44 Correct 319 ms 183804 KB Output is correct
45 Correct 287 ms 184936 KB Output is correct
46 Correct 278 ms 184772 KB Output is correct
47 Correct 272 ms 183236 KB Output is correct
48 Correct 277 ms 184632 KB Output is correct
49 Correct 305 ms 182532 KB Output is correct
50 Correct 284 ms 184188 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 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 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 13128 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 4 ms 13912 KB Output is correct
17 Correct 4 ms 13912 KB Output is correct
18 Correct 4 ms 13860 KB Output is correct
19 Correct 18 ms 23204 KB Output is correct
20 Correct 17 ms 23132 KB Output is correct
21 Correct 18 ms 23132 KB Output is correct
22 Correct 16 ms 22108 KB Output is correct
23 Correct 18 ms 22620 KB Output is correct
24 Correct 14 ms 22108 KB Output is correct
25 Correct 13 ms 21852 KB Output is correct
26 Correct 15 ms 22032 KB Output is correct
27 Correct 2150 ms 752504 KB Output is correct
28 Correct 2238 ms 751748 KB Output is correct
29 Correct 2289 ms 753140 KB Output is correct
30 Correct 2145 ms 751612 KB Output is correct
31 Correct 1375 ms 439480 KB Output is correct
32 Correct 1315 ms 641620 KB Output is correct
33 Correct 1601 ms 660216 KB Output is correct
34 Correct 1507 ms 653396 KB Output is correct
35 Correct 2 ms 12632 KB Output is correct
36 Correct 641 ms 196656 KB Output is correct
37 Correct 2410 ms 663088 KB Output is correct
38 Correct 2356 ms 664340 KB Output is correct
39 Correct 2793 ms 672624 KB Output is correct
40 Correct 1193 ms 349000 KB Output is correct
41 Correct 539 ms 182704 KB Output is correct
42 Correct 62 ms 50292 KB Output is correct
43 Correct 2444 ms 666696 KB Output is correct
44 Execution timed out 3044 ms 685968 KB Time limit exceeded
45 Halted 0 ms 0 KB -