oj.uz

Submission #855761

# Submission time Handle Problem Language Result Execution time Memory
855761 2023-10-01T18:13:28 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
72 / 100
 3000 ms 482256 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() & 3; }
 
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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 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 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 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 2 ms 7260 KB Output is correct
19 Correct 8 ms 11972 KB Output is correct
20 Correct 9 ms 11868 KB Output is correct
21 Correct 10 ms 11868 KB Output is correct
22 Correct 10 ms 12892 KB Output is correct
23 Correct 14 ms 14172 KB Output is correct
24 Correct 9 ms 12892 KB Output is correct
25 Correct 8 ms 12380 KB Output is correct
26 Correct 9 ms 12632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 349956 KB Output is correct
2 Correct 798 ms 350388 KB Output is correct
3 Correct 773 ms 349756 KB Output is correct
4 Correct 818 ms 351412 KB Output is correct
5 Correct 604 ms 184236 KB Output is correct
6 Correct 796 ms 373216 KB Output is correct
7 Correct 813 ms 356796 KB Output is correct
8 Correct 832 ms 360628 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 482 ms 136296 KB Output is correct
3 Correct 1754 ms 480212 KB Output is correct
4 Correct 1625 ms 478900 KB Output is correct
5 Correct 2234 ms 471572 KB Output is correct
6 Correct 766 ms 222400 KB Output is correct
7 Correct 279 ms 111232 KB Output is correct
8 Correct 35 ms 30160 KB Output is correct
9 Correct 1910 ms 482256 KB Output is correct
10 Execution timed out 3053 ms 454584 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 464316 KB Output is correct
2 Correct 672 ms 393912 KB Output is correct
3 Correct 1675 ms 363904 KB Output is correct
4 Correct 730 ms 401736 KB Output is correct
5 Correct 708 ms 396500 KB Output is correct
6 Correct 1206 ms 353096 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 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 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 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 2 ms 7260 KB Output is correct
19 Correct 8 ms 11972 KB Output is correct
20 Correct 9 ms 11868 KB Output is correct
21 Correct 10 ms 11868 KB Output is correct
22 Correct 10 ms 12892 KB Output is correct
23 Correct 14 ms 14172 KB Output is correct
24 Correct 9 ms 12892 KB Output is correct
25 Correct 8 ms 12380 KB Output is correct
26 Correct 9 ms 12632 KB Output is correct
27 Correct 22 ms 17244 KB Output is correct
28 Correct 16 ms 17240 KB Output is correct
29 Correct 16 ms 17240 KB Output is correct
30 Correct 24 ms 20828 KB Output is correct
31 Correct 19 ms 19416 KB Output is correct
32 Correct 19 ms 19292 KB Output is correct
33 Correct 184 ms 92524 KB Output is correct
34 Correct 204 ms 92712 KB Output is correct
35 Correct 215 ms 92612 KB Output is correct
36 Correct 270 ms 118888 KB Output is correct
37 Correct 272 ms 119492 KB Output is correct
38 Correct 310 ms 123756 KB Output is correct
39 Correct 162 ms 13088 KB Output is correct
40 Correct 164 ms 12996 KB Output is correct
41 Correct 162 ms 13124 KB Output is correct
42 Correct 177 ms 14152 KB Output is correct
43 Correct 197 ms 106952 KB Output is correct
44 Correct 196 ms 105412 KB Output is correct
45 Correct 199 ms 106820 KB Output is correct
46 Correct 220 ms 106608 KB Output is correct
47 Correct 195 ms 104644 KB Output is correct
48 Correct 199 ms 106540 KB Output is correct
49 Correct 189 ms 104136 KB Output is correct
50 Correct 192 ms 105672 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 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 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 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 2 ms 7260 KB Output is correct
19 Correct 8 ms 11972 KB Output is correct
20 Correct 9 ms 11868 KB Output is correct
21 Correct 10 ms 11868 KB Output is correct
22 Correct 10 ms 12892 KB Output is correct
23 Correct 14 ms 14172 KB Output is correct
24 Correct 9 ms 12892 KB Output is correct
25 Correct 8 ms 12380 KB Output is correct
26 Correct 9 ms 12632 KB Output is correct
27 Correct 787 ms 349956 KB Output is correct
28 Correct 798 ms 350388 KB Output is correct
29 Correct 773 ms 349756 KB Output is correct
30 Correct 818 ms 351412 KB Output is correct
31 Correct 604 ms 184236 KB Output is correct
32 Correct 796 ms 373216 KB Output is correct
33 Correct 813 ms 356796 KB Output is correct
34 Correct 832 ms 360628 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 482 ms 136296 KB Output is correct
37 Correct 1754 ms 480212 KB Output is correct
38 Correct 1625 ms 478900 KB Output is correct
39 Correct 2234 ms 471572 KB Output is correct
40 Correct 766 ms 222400 KB Output is correct
41 Correct 279 ms 111232 KB Output is correct
42 Correct 35 ms 30160 KB Output is correct
43 Correct 1910 ms 482256 KB Output is correct
44 Execution timed out 3053 ms 454584 KB Time limit exceeded
45 Halted 0 ms 0 KB -