oj.uz

Submission #853271

# Submission time Handle Problem Language Result Execution time Memory
853271 2023-09-23T19:49:09 Z dlalswp25 Circle selection (APIO18_circle_selection) C++17
15 / 100
 3000 ms 529396 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int K = 3;

int N;
int XL[303030];
int XR[303030];
vector<pii> UL[303030];
vector<pii> UR[303030];
vector<int> V[303030];
int ans[303030];

struct Circle {
	int x, y, r, id;
} A[303030];

struct DSU {
	int n;
	vector<int> l, r;

	DSU(int _n = 0) : n(_n), l(_n), r(_n) {
		for (int i = 0; i < n; i++) l[i] = r[i] = i;
	}

	int left(int x) {
		x = min(x, n - 1);
		if (x < 0 || x == l[x]) return x;
		return l[x] = left(l[x]);
	}

	int right(int x) {
		x = max(x, 0);
		if (x >= n || x == r[x]) return x;
		return r[x] = right(r[x]);
	}

	void upd(int x) {
		l[x] = x - 1; r[x] = x + 1;
	}
};

bool intersect(int i, int j) {
	int dx = A[i].x - A[j].x, dy = A[i].y - A[j].y, r = A[i].r + A[j].r;
	return (long long)dx * dx + (long long)dy * dy <= (long long)r * r;
}

void upd_ans(int cur, int cand) {
	int &t = ans[cur];
	if (A[t].r > A[cand].r || (A[t].r == A[cand].r && 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].push_back(T[p].v.size());
				T[p].v.emplace_back(y, i);
				p++;
			}
			if (~q & 1) {
				V[i].push_back(T[q].v.size());
				T[q].v.emplace_back(y, i);
				q--;
			}
			p >>= 1; q >>= 1;
		}
	}

	void add_point(int p, vector<pii> &v) {
		p += base; p--;
		while (p) {
			v.emplace_back(p, 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 ers_line(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, vector<pii> &v) {
		for (auto &i : v) {
			int p, s; tie(p, s) = 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() {
	scanf("%d", &N);
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].r);
		XL[i] = A[i].x - A[i].r;
		XR[i] = A[i].x + A[i].r;
		v.push_back(XL[i]); v.push_back(XR[i]);
		A[i].id = 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);

	sort(A + 1, A + N + 1, [&](Circle &a, Circle &b) {
		return a.y < b.y;
	});
	for (int i = 1; i <= N; i++) {
		int j = A[i].id;
		seg.add_line(XL[j], XR[j], A[i].y, j);
		seg.add_point(XL[j], UL[j]);
		seg.add_point(XR[j], UR[j]);
	}
	seg.init();
	sort(A + 1, A + N + 1, [&](Circle &a, Circle &b) {
		return a.id < b.id;
	});

	vector<int> ord(N);
	iota(ord.begin(), ord.end(), 1);
	sort(ord.begin(), ord.end(), [&](int a, int b) {
		if (A[a].r == A[b].r) return a < b;
		return A[a].r > A[b].r;
	});

	for (int i : ord) {
		ans[i] = i;
		seg.chk(i, UL[i]);
		seg.chk(i, UR[i]);
		if (ans[i] != i) seg.ers_line(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, std::vector<std::pair<int, int> >&)':
circle_selection.cpp:123:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     if (t >= T[p].v.size()) break;
      |         ~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:186:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  186 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |  ^~~
circle_selection.cpp:186:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  186 |  for (int i = 1; i <= N; i++) printf("%d ", ans[i]); puts("");
      |                                                      ^~~~
circle_selection.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24920 KB Output is correct
4 Correct 5 ms 24920 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Incorrect 5 ms 24920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 529396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 601 ms 153548 KB Output is correct
3 Correct 2181 ms 450104 KB Output is correct
4 Correct 2144 ms 449800 KB Output is correct
5 Correct 2503 ms 454356 KB Output is correct
6 Correct 1165 ms 248536 KB Output is correct
7 Correct 488 ms 137792 KB Output is correct
8 Correct 57 ms 50380 KB Output is correct
9 Correct 2245 ms 453044 KB Output is correct
10 Correct 2988 ms 471880 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1818 ms 445384 KB Output is correct
2 Correct 1145 ms 412708 KB Output is correct
3 Execution timed out 3032 ms 500776 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24920 KB Output is correct
4 Correct 5 ms 24920 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Incorrect 5 ms 24920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 24920 KB Output is correct
3 Correct 5 ms 24920 KB Output is correct
4 Correct 5 ms 24920 KB Output is correct
5 Correct 5 ms 24920 KB Output is correct
6 Incorrect 5 ms 24920 KB Output isn't correct
7 Halted 0 ms 0 KB -