oj.uz

Submission #854738

# Submission time Handle Problem Language Result Execution time Memory
854738 2023-09-28T17:18:00 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
49 / 100
 3000 ms 716456 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, 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:161: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]
  161 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:179: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]
  179 |      if (t >= T[p].v.size()) break;
      |          ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:236:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  236 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:236:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  236 |  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 1 ms 12636 KB Output is correct
5 Correct 1 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 12848 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 12892 KB Output is correct
14 Correct 2 ms 12636 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 4 ms 13916 KB Output is correct
19 Correct 15 ms 22872 KB Output is correct
20 Correct 16 ms 22876 KB Output is correct
21 Correct 16 ms 22872 KB Output is correct
22 Correct 12 ms 21852 KB Output is correct
23 Correct 17 ms 22320 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 11 ms 21596 KB Output is correct
26 Correct 13 ms 21848 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2279 ms 712908 KB Output is correct
2 Correct 2348 ms 714484 KB Output is correct
3 Correct 2381 ms 716456 KB Output is correct
4 Correct 2316 ms 712812 KB Output is correct
5 Correct 1426 ms 423984 KB Output is correct
6 Correct 1345 ms 617924 KB Output is correct
7 Correct 1662 ms 627592 KB Output is correct
8 Correct 1539 ms 626120 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 646 ms 197240 KB Output is correct
3 Correct 2233 ms 640512 KB Output is correct
4 Correct 2201 ms 640124 KB Output is correct
5 Correct 2591 ms 645588 KB Output is correct
6 Correct 1159 ms 338596 KB Output is correct
7 Correct 469 ms 178380 KB Output is correct
8 Correct 54 ms 48344 KB Output is correct
9 Correct 2281 ms 643628 KB Output is correct
10 Execution timed out 3032 ms 659696 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 635316 KB Output is correct
2 Correct 1122 ms 604216 KB Output is correct
3 Execution timed out 3024 ms 688560 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 1 ms 12636 KB Output is correct
5 Correct 1 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 12848 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 12892 KB Output is correct
14 Correct 2 ms 12636 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 4 ms 13916 KB Output is correct
19 Correct 15 ms 22872 KB Output is correct
20 Correct 16 ms 22876 KB Output is correct
21 Correct 16 ms 22872 KB Output is correct
22 Correct 12 ms 21852 KB Output is correct
23 Correct 17 ms 22320 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 11 ms 21596 KB Output is correct
26 Correct 13 ms 21848 KB Output is correct
27 Correct 31 ms 33116 KB Output is correct
28 Correct 32 ms 33228 KB Output is correct
29 Correct 33 ms 33228 KB Output is correct
30 Correct 32 ms 31824 KB Output is correct
31 Correct 26 ms 31068 KB Output is correct
32 Correct 26 ms 31068 KB Output is correct
33 Correct 564 ms 215776 KB Output is correct
34 Correct 637 ms 217248 KB Output is correct
35 Correct 650 ms 218820 KB Output is correct
36 Correct 459 ms 190916 KB Output is correct
37 Correct 479 ms 191552 KB Output is correct
38 Correct 508 ms 193148 KB Output is correct
39 Correct 160 ms 72348 KB Output is correct
40 Correct 166 ms 72388 KB Output is correct
41 Correct 164 ms 72312 KB Output is correct
42 Correct 206 ms 76052 KB Output is correct
43 Correct 305 ms 185488 KB Output is correct
44 Correct 307 ms 184472 KB Output is correct
45 Correct 308 ms 185324 KB Output is correct
46 Correct 304 ms 185248 KB Output is correct
47 Correct 309 ms 183684 KB Output is correct
48 Correct 302 ms 185280 KB Output is correct
49 Correct 310 ms 183236 KB Output is correct
50 Correct 304 ms 184256 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 1 ms 12636 KB Output is correct
5 Correct 1 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 12848 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 12892 KB Output is correct
14 Correct 2 ms 12636 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 4 ms 13916 KB Output is correct
19 Correct 15 ms 22872 KB Output is correct
20 Correct 16 ms 22876 KB Output is correct
21 Correct 16 ms 22872 KB Output is correct
22 Correct 12 ms 21852 KB Output is correct
23 Correct 17 ms 22320 KB Output is correct
24 Correct 13 ms 21852 KB Output is correct
25 Correct 11 ms 21596 KB Output is correct
26 Correct 13 ms 21848 KB Output is correct
27 Correct 2279 ms 712908 KB Output is correct
28 Correct 2348 ms 714484 KB Output is correct
29 Correct 2381 ms 716456 KB Output is correct
30 Correct 2316 ms 712812 KB Output is correct
31 Correct 1426 ms 423984 KB Output is correct
32 Correct 1345 ms 617924 KB Output is correct
33 Correct 1662 ms 627592 KB Output is correct
34 Correct 1539 ms 626120 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 646 ms 197240 KB Output is correct
37 Correct 2233 ms 640512 KB Output is correct
38 Correct 2201 ms 640124 KB Output is correct
39 Correct 2591 ms 645588 KB Output is correct
40 Correct 1159 ms 338596 KB Output is correct
41 Correct 469 ms 178380 KB Output is correct
42 Correct 54 ms 48344 KB Output is correct
43 Correct 2281 ms 643628 KB Output is correct
44 Execution timed out 3032 ms 659696 KB Time limit exceeded
45 Halted 0 ms 0 KB -