제출 #103202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103202		E869120	원 고르기 (APIO18_circle_selection)	C++14	7 / 100	3114 ms	275908 KiB

circle_selection

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	int val, num, l, r;
};

class SegmentTree {
public:
	vector<Node>vec; vector<int>V; long long lx, ly, rx, ry;

	void init() {
		vec.push_back(Node{ 0, 0, -1, -1 });
	}
	void add(long long px, long long py, int NN) {
		int cx = 0;
		for (int i = 61; i >= 0; i--) {
			vec[cx].val += 1;
			if (i >= 31) {
				int dep = i - 31;
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = i;
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val++; vec[cx].num = NN;
	}
	void lose(long long px, long long py, int NN) {
		int cx = 0;
		for (int i = 61; i >= 0; i--) {
			vec[cx].val -= 1;
			if (i >= 31) {
				int dep = i - 31;
				if (px >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].r; px -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].l;
				}
			}
			else {
				int dep = i;
				if (py >= (1LL << dep)) {
					if (vec[cx].r == -1) { vec[cx].r = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].r; py -= (1LL << dep);
				}
				else {
					if (vec[cx].l == -1) { vec[cx].l = vec.size(); vec.push_back(Node{ 0, 0, -1,-1 }); }
					cx = vec[cx].l;
				}
			}
		}
		vec[cx].val--; vec[cx].num = 0;
	}
	void query_(long long ax, long long ay, long long bx, long long by, int dep, int u) {
		if (vec[u].val == 0) return;
		if (rx <= ax || bx <= lx || ry <= ay || by <= ly) return;
		if (dep == 0) {
			V.push_back(vec[u].num);
			return;
		}

		if (dep >= 32) {
			if (vec[u].l >= 0) query_(ax, ay, (ax + bx) >> 1, by, dep - 1, vec[u].l);
			if (vec[u].r >= 0) query_((ax + bx) >> 1, ay, bx, by, dep - 1, vec[u].r);
		}
		else {
			if (vec[u].l >= 0) query_(ax, ay, bx, (ay + by) >> 1, dep - 1, vec[u].l);
			if (vec[u].r >= 0) query_(ax, (ay + by) >> 1, bx, by, dep - 1, vec[u].r);
		}
	}
	vector<int> query(long long LX, long long LY, long long RX, long long RY) {
		LX = max(LX, 0LL); LY = max(LY, 0LL); RX = min(RX, (1LL << 31)); RY = min(RY, (1LL << 31));
		lx = LX; ly = LY; rx = RX; ry = RY;
		V.clear();
		query_(0, 0, (1LL << 31), (1LL << 31), 62, 0);
		return V;
	}
};

long long N, X[1 << 19], Y[1 << 19], R[1 << 19], score[1 << 19];
bool used[1 << 19];

long long dist(int p1, int p2) {
	return (X[p1] - X[p2]) * (X[p1] - X[p2]) + abs(Y[p1] - Y[p2]) * abs(Y[p1] - Y[p2]);
}

void solve_Jury() {
	while (true) {
		int maxn = -1, id = -1;
		for (int i = 1; i <= N; i++) {
			if (used[i] == true) continue;
			if (maxn < R[i]) { maxn = R[i]; id = i; }
		}

		if (id == -1) break;

		for (int i = 1; i <= N; i++) {
			if (used[i] == true) continue;
			if (dist(id, i) <= (R[i] + R[id]) * (R[i] + R[id])) { used[i] = true; score[i] = id; }
		}
	}
}

bool uses[1 << 19]; SegmentTree Z;

void solve_subtasks() {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, less<pair<long long, int>>>Q;
	Z.init();
	for (int i = 1; i <= N; i++) Q.push(make_pair(R[i], -i));
	for (int i = 1; i <= N; i++) Z.add(X[i], Y[i], i);

	while (!Q.empty()) {
		int pos = -Q.top().second;
		vector<int>E = Z.query(X[pos] - 2LL * R[pos], Y[pos] - 2LL * R[pos], X[pos] + 2LL * R[pos] + 1LL, Y[pos] + 2LL * R[pos] + 1LL);

		for (int i = 0; i < E.size(); i++) {
			if (dist(pos, E[i]) <= 1LL * (R[pos] + R[E[i]]) * (R[pos] + R[E[i]])) {
				Z.lose(X[E[i]], Y[E[i]], E[i]);
				used[E[i]] = true;
				score[E[i]] = pos;
			}
		}
		while (!Q.empty()) { int pos = -Q.top().second; if (used[pos] == false) break; Q.pop(); }
	}
}

int main() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) { scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]); X[i] += (1LL << 30); Y[i] += (1LL << 30); }

	if (N <= 5000) {
		solve_Jury();
	}

	else {
		solve_subtasks();
	}

	for (int i = 1; i <= N; i++) {
		if (i >= 2) printf(" ");
		printf("%lld", score[i]);
	}
	printf("\n");
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
circle_selection.cpp: In function 'void solve_subtasks()':
circle_selection.cpp:138:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < E.size(); i++) {
                   ~~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~
circle_selection.cpp:151:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) { scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]); X[i] += (1LL << 30); Y[i] += (1LL << 30); }
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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