oj.uz

Submission #855011

# Submission time Handle Problem Language Result Execution time Memory
855011 2023-09-29T19:31:09 Z dlalswp25 Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 615344 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;

random_device rd;
mt19937 rng(rd());

const int INF = 1010101010;
const int K = 2;

int N;
int X[303030];
int Y[303030];
int R[303030];
int XL[303030];
int XR[303030];
int ans[303030];
int cur;
char rr;

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;
}

int gen() { return rng() & 1; }

inline bool intersect(int i, int j) {
	long long dx = X[i] - X[j], dy = Y[i] - Y[j], r = R[i] + R[j];
	return dx * dx + dy * dy <= r * r;
}

inline void chk(int cand) {
	int &t = ans[cur];
	if (R[cand] < R[t] || (R[cand] == R[t] && cand > t)) return;
	if (intersect(cur, cand)) t = cand;
}

struct SkipList {
	struct Node {
		pii v;
		Node *l, *r, *d;

		Node(pii _v) : v(_v), l(nullptr), r(nullptr), d(nullptr) {}
	};

	struct Layer {
		Node *head;

		Layer() {
			head = new Node({-INF, 0});
			head->r = new Node({INF, 0});
			head->r->l = head;
		}
	};

	int height;
	vector<Layer> V;

	SkipList() { V.push_back(Layer()); }

	Node *lower_bound(pii x) {
		Node *cur = V.back().head;
		int h = V.size();
		for (int i = h - 1; i >= 0; i--) {
			while (cur->r->v < x) cur = cur->r;
			if (i) cur = cur->d;
		}
		return cur->r;
	}

	void insert(pii x) {
		Node *cur = V.back().head;
		int h = V.size();
		vector<Node *> lst(h);
		for (int i = h - 1; i >= 0; i--) {
			while (cur->r->v < x) cur = cur->r;
			lst[i] = cur;
			if (i) cur = cur->d;
		}
		Node *bef = nullptr;
		for (int i = 0; ; i++) {
			if (i < h) {
				cur = lst[i];
			} else {
				V.push_back(Layer());
				cur = V.back().head;
				V[i].head->d = V[i - 1].head;
			}
			Node *tmp = cur->r;
			cur->r = new Node(x);
			cur->r->r = tmp;
			cur->r->l = cur;
			tmp->l = cur->r;
			cur->r->d = bef;
			bef = cur;
			if (gen()) break;
		}
	}

	void print() {
		for (int i = 0; i < V.size(); i++) {
			printf("level %d\n", i);
			Node *cur = V[i].head;
			while (cur) {
				printf("(%d %d; %d) ", cur->v.first, cur->v.second, !!cur->d);
				cur = cur->r;
			}
			puts("");
		}
	}
};

struct SegTree {
	struct Node {
		SkipList s;
	};

	int n, base;
	vector<Node> T;
	vector<int> L;

	SegTree(int _n) : n(_n) {
		for (base = 1; base < n; base <<= 1);
		T.resize(base + base);
		L.resize(base + base);
		for (int i = base; i < base + base; i++) L[i] = i - base + 1;
		for (int i = base - 1; i >= 1; i--) L[i] = L[i << 1];
	}

	void chk_node(int idx, int r, int li) {
		int y = Y[cur];
		auto it = T[idx].s.lower_bound({y, 0});
		auto tmp = it;
		for (int i = 0; i < K; i++) {
			if (it->v.first == INF) break;
			if (XL[it->v.second] <= li) break;
			chk(it->v.second);
			if (it->v.first >= (long long)y + r + r) break;
			if (i < K - 1) it = it->r;
		}
		it = tmp;
		for (int i = 0; i < K; i++) {
			it = it->l;
			if (it->v.first == -INF) break;
			if (XL[it->v.second] <= li) break;
			chk(it->v.second);
			if (it->v.first <= (long long)y - r - r) break;
		}
	}

	void upd(int p, int q, pii x) {
		p += base; q += base;
		p--; q--;
		while (p <= q) {
			if (p & 1) T[p++].s.insert(x);
			if (~q & 1) T[q--].s.insert(x);
			p >>= 1; q >>= 1;
		}
	}

	void get(int p, int r, int li) {
		p += base; p--;
		while (p >= 1) {
			if (L[p] <= li) break;
			chk_node(p, r, li);
			p >>= 1;
		}
	}
};

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> idx(N);
	iota(idx.begin(), idx.end(), 1);
	sort(idx.begin(), idx.end(), [&](int a, int b) {
		return pii(R[a], -a) > pii(R[b], -b);
	});

	for (int i : idx) {
		cur = i;
		ans[i] = i;
		seg.get(XL[i], R[i], 0);
		seg.get(XR[i], R[i], XL[i]);
		if (ans[i] == i) seg.upd(XL[i], XR[i], {Y[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 SkipList::print()':
circle_selection.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<SkipList::Layer>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 0; i < V.size(); i++) {
      |                   ~~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:212:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  212 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:212:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  212 |  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 1 ms 6596 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6600 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6600 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6596 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6600 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 8 ms 12124 KB Output is correct
20 Correct 8 ms 12120 KB Output is correct
21 Correct 10 ms 12120 KB Output is correct
22 Correct 11 ms 14172 KB Output is correct
23 Correct 22 ms 16588 KB Output is correct
24 Correct 10 ms 14000 KB Output is correct
25 Correct 9 ms 13148 KB Output is correct
26 Correct 11 ms 13752 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 356444 KB Output is correct
2 Correct 812 ms 356952 KB Output is correct
3 Correct 793 ms 356288 KB Output is correct
4 Correct 772 ms 357184 KB Output is correct
5 Correct 591 ms 190648 KB Output is correct
6 Correct 827 ms 400992 KB Output is correct
7 Correct 798 ms 367028 KB Output is correct
8 Correct 806 ms 375404 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 576 ms 180220 KB Output is correct
3 Correct 2001 ms 610060 KB Output is correct
4 Correct 2033 ms 609544 KB Output is correct
5 Correct 2676 ms 588604 KB Output is correct
6 Correct 991 ms 268480 KB Output is correct
7 Correct 381 ms 132472 KB Output is correct
8 Correct 37 ms 32976 KB Output is correct
9 Correct 2308 ms 615344 KB Output is correct
10 Execution timed out 3051 ms 550912 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1519 ms 580740 KB Output is correct
2 Correct 745 ms 448412 KB Output is correct
3 Correct 2057 ms 385492 KB Output is correct
4 Correct 803 ms 463920 KB Output is correct
5 Correct 761 ms 455116 KB Output is correct
6 Correct 1370 ms 365500 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6596 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6600 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6600 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6596 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6600 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 8 ms 12124 KB Output is correct
20 Correct 8 ms 12120 KB Output is correct
21 Correct 10 ms 12120 KB Output is correct
22 Correct 11 ms 14172 KB Output is correct
23 Correct 22 ms 16588 KB Output is correct
24 Correct 10 ms 14000 KB Output is correct
25 Correct 9 ms 13148 KB Output is correct
26 Correct 11 ms 13752 KB Output is correct
27 Correct 16 ms 17496 KB Output is correct
28 Correct 16 ms 17500 KB Output is correct
29 Correct 16 ms 17500 KB Output is correct
30 Correct 40 ms 24912 KB Output is correct
31 Correct 28 ms 21852 KB Output is correct
32 Correct 21 ms 21588 KB Output is correct
33 Correct 193 ms 95612 KB Output is correct
34 Correct 222 ms 95848 KB Output is correct
35 Correct 215 ms 95684 KB Output is correct
36 Correct 340 ms 147772 KB Output is correct
37 Correct 323 ms 149680 KB Output is correct
38 Correct 384 ms 158144 KB Output is correct
39 Correct 193 ms 16500 KB Output is correct
40 Correct 197 ms 16456 KB Output is correct
41 Correct 202 ms 16428 KB Output is correct
42 Correct 199 ms 18368 KB Output is correct
43 Correct 223 ms 125068 KB Output is correct
44 Correct 207 ms 121796 KB Output is correct
45 Correct 232 ms 124524 KB Output is correct
46 Correct 228 ms 124360 KB Output is correct
47 Correct 209 ms 120516 KB Output is correct
48 Correct 213 ms 124100 KB Output is correct
49 Correct 239 ms 119244 KB Output is correct
50 Correct 229 ms 122568 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6596 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6600 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6600 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6596 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6600 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 3 ms 7260 KB Output is correct
19 Correct 8 ms 12124 KB Output is correct
20 Correct 8 ms 12120 KB Output is correct
21 Correct 10 ms 12120 KB Output is correct
22 Correct 11 ms 14172 KB Output is correct
23 Correct 22 ms 16588 KB Output is correct
24 Correct 10 ms 14000 KB Output is correct
25 Correct 9 ms 13148 KB Output is correct
26 Correct 11 ms 13752 KB Output is correct
27 Correct 782 ms 356444 KB Output is correct
28 Correct 812 ms 356952 KB Output is correct
29 Correct 793 ms 356288 KB Output is correct
30 Correct 772 ms 357184 KB Output is correct
31 Correct 591 ms 190648 KB Output is correct
32 Correct 827 ms 400992 KB Output is correct
33 Correct 798 ms 367028 KB Output is correct
34 Correct 806 ms 375404 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 576 ms 180220 KB Output is correct
37 Correct 2001 ms 610060 KB Output is correct
38 Correct 2033 ms 609544 KB Output is correct
39 Correct 2676 ms 588604 KB Output is correct
40 Correct 991 ms 268480 KB Output is correct
41 Correct 381 ms 132472 KB Output is correct
42 Correct 37 ms 32976 KB Output is correct
43 Correct 2308 ms 615344 KB Output is correct
44 Execution timed out 3051 ms 550912 KB Time limit exceeded
45 Halted 0 ms 0 KB -