Submission #854712

#	Time	Username	Problem	Language	Result	Execution time	Memory
854712		dlalswp25	Circle selection (APIO18_circle_selection)	C++17	49 / 100	3044 ms	753140 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;

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

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