Submission #453731

#	Time	Username	Problem	Language	Result	Execution time	Memory
453731		arminatarod	Circle selection (APIO18_circle_selection)	C++17	12 / 100	995 ms	45240 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 300005;

constexpr int MAXINT = 1073741823;

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

int sorted[MAXN], answer[MAXN];

bitset<MAXN> deleted;

set<pair<int, int>> lefts;

set<pair<int, int>, greater<pair<int, int>>> rights;

set<pair<int, int>>::iterator it1;

set<pair<int, int>, greater<pair<int, int>>>::iterator it2;

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

vector<int> to_delete;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> circle[i].x >> circle[i].y >> circle[i].radius;
		lefts.emplace(circle[i].x - circle[i].radius, i);
		rights.emplace(circle[i].x + circle[i].radius, i);
		sorted[i] = i;
	}
	sort(sorted, sorted + n, comparison);
	for (int i = 0; i < n; i++)
		if (!deleted[sorted[i]]) {
			to_delete.clear();
			it1 = lefts.lower_bound(make_pair(circle[sorted[i]].x - circle[sorted[i]].radius, 0));
			while (it1 != lefts.end() && it1->first <= circle[sorted[i]].x + circle[sorted[i]].radius) {
				to_delete.push_back(it1->second);
				it1++;
			}
			it2 = rights.lower_bound(make_pair(circle[sorted[i]].x + circle[sorted[i]].radius, MAXINT));
			while (it2 != rights.end() && it2->first >= circle[sorted[i]].x - circle[sorted[i]].radius) {
				to_delete.push_back(it2->second);
				it2++;
			}
			for (int j : to_delete) {
				lefts.erase(make_pair(circle[j].x - circle[j].radius, j));
				rights.erase(make_pair(circle[j].x + circle[j].radius, j));
				answer[j] = sorted[i];
				deleted[j] = true;
			}
		}
	for (int i = 0; i < n; i++)
		cout << answer[i] + 1 << ' ';
	return 0;
}

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