Submission #453704

#	Time	Username	Problem	Language	Result	Execution time	Memory
453704		arminatarod	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3095 ms	331472 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 300005;

constexpr int MAXINT = 1073741823;

vector<int> all_numbers;

struct circles {
	long long int x, y, radius;
} circle[MAXN];

int sorted[MAXN], answer[MAXN];

bitset<MAXN> deleted;

set<int> segment[MAXN * 8];

bool comparison(int x, int y) {
	return (circle[x].radius == circle[y].radius? x < y : circle[x].radius > circle[y].radius);
}

void add(int from, int to, int current, int index, int value) {
	if (from > index || to < index)
		return;
	segment[current].insert(value);
	if (from == to)
		return;
	int mid = (from + to) / 2;
	add(from, mid, current * 2 + 1, index, value);
	add(mid + 1, to, current * 2 + 2, index, value);
	return;
}

void eliminate(int from, int to, int current, int index, int value) {
	if (from > index || to < index)
		return;
	segment[current].erase(value);
	if (from == to)
		return;
	int mid = (from + to) / 2;
	add(from, mid, current * 2 + 1, index, value);
	add(mid + 1, to, current * 2 + 2, index, value);
	return;
}

vector<int> selection, to_delete;

void select(int from, int to, int current, int beginning, int ending) {
	if (from > ending || to < beginning)
		return;
	else if (beginning <= from && to <= ending) {
		selection.push_back(current);
		return;
	}
	int mid = (from + to) / 2;
	select(from, mid, current * 2 + 1, beginning, ending);
	select(mid + 1, to, current * 2 + 2, beginning, ending);
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n, from, to;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> circle[i].x >> circle[i].y >> circle[i].radius;
		all_numbers.push_back(circle[i].x - circle[i].radius);
		all_numbers.push_back(circle[i].x + circle[i].radius);
		sorted[i] = i;
	}
	sort(sorted, sorted + n, comparison);
	sort(all_numbers.begin(), all_numbers.end());
	all_numbers.resize(distance(all_numbers.begin(), unique(all_numbers.begin(), all_numbers.end())));
	for (int i = 0; i < n; i++) {
		from = lower_bound(all_numbers.begin(), all_numbers.end(), circle[i].x - circle[i].radius) - all_numbers.begin();
		to = lower_bound(all_numbers.begin(), all_numbers.end(), circle[i].x + circle[i].radius) - all_numbers.begin();
		add(0, all_numbers.size() - 1, 0, from, i);
		add(0, all_numbers.size() - 1, 0, to, i);
	}
	for (int i = 0; i < n; i++)
		if (!deleted[sorted[i]]) {
			deleted[sorted[i]] = true;
			selection.clear();
			from = lower_bound(all_numbers.begin(), all_numbers.end(), circle[sorted[i]].x - circle[sorted[i]].radius) - all_numbers.begin();
			to = lower_bound(all_numbers.begin(), all_numbers.end(), circle[sorted[i]].x + circle[sorted[i]].radius) - all_numbers.begin();
			select(0, all_numbers.size() - 1, 0, from, to);
			to_delete.clear();
			for (int j : selection)
				to_delete.insert(to_delete.end(), segment[j].begin(), segment[j].end());
			for (int j : to_delete) {
				answer[j] = sorted[i];
				deleted[j] = true;
				from = lower_bound(all_numbers.begin(), all_numbers.end(), circle[j].x - circle[j].radius) - all_numbers.begin();
				to = lower_bound(all_numbers.begin(), all_numbers.end(), circle[j].x + circle[j].radius) - all_numbers.begin();
				eliminate(0, all_numbers.size() - 1, 0, from, j);
				eliminate(0, all_numbers.size() - 1, 0, to, j);
			}
		}
	for (int i = 0; i < n; i++)
		cout << answer[i] + 1 << ' ';
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13