oj.uz

Submission #453729

# Submission time Handle Problem Language Result Execution time Memory
453729 2021-08-04T16:10:17 Z arminatarod Circle selection (APIO18_circle_selection) C++17
0 / 100
 915 ms 38300 KB 
#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.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 915 ms 38300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 737 ms 36084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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