Submission #855761

#	Time	Username	Problem	Language	Result	Execution time	Memory
855761		dlalswp25	Circle selection (APIO18_circle_selection)	C++17	72 / 100	3053 ms	482256 KiB

circle_selection

#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 (stderr)

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13