답안 #95385 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95385	2019-01-31T08:15:03 Z	pranjalssh	원 고르기 (APIO18_circle_selection)	C++14	87 / 100	3000 ms	89088 KB

circle_selection

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


const int N = 3e5 + 10;
vi x, y, r;
struct node {
	int l, r, sum;
	vector<int> a;
	node(): l(0), r(0), sum(0) {}
};
vector<node> T;
vi xc, yc;
vi par;
inline bool intersect(int i, int j) {
	return (x[i] - x[j]) * 1LL * (x[i] - x[j]) + (y[i] - y[j]) * 1LL * (y[i] - y[j]) <= (r[i] + r[j]) * 1LL * (r[i] + r[j]);
}

inline int make_node() {
	T.emplace_back();
	return sz(T) - 1;
}

int build(int no, bool dim, int xl, int xr, int yl, int yr, const vi& ids) {
	if (ids.empty()) return no;
	if (no == 0) no = make_node();
	bool g = 1;
	FOR (i, 1, sz(ids) - 1) if (x[ids[i]] != x[ids[0]] or y[ids[i]] != y[ids[0]]) {g = 0; break;}
	if (g) {
		T[no].sum = sz(ids);
		T[no].a = ids;
		return no;
	}
	if (dim) {
		int mid = (yl + yr) >> 1;
		vi lids, rids;
		for (int it : ids) {
			if (y[it] <= mid) lids.emplace_back(it);
			else rids.emplace_back(it);
		}
		int L = build(0, 0, xl, xr, yl, mid, lids);
		int R = build(0, 0, xl, xr, mid + 1, yr, rids);
		T[no].l = L, T[no].r = R;
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	} else {
		int mid = (xl + xr) >> 1;
		vi lids, rids;
		for (int it : ids) {
			if (x[it] <= mid) lids.emplace_back(it);
			else rids.emplace_back(it);
		}
		int L = build(0, 1, xl, mid, yl, yr, lids);
		int R = build(0, 1, mid + 1, xr, yl, yr, rids);
		T[no].l = L, T[no].r = R;
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	}
	return no;
}

int xu, xv, yu, yv, bc;
vi rem;

void get(int no, bool dim, int xl, int xr, int yl, int yr) {
	// pr(no, xl, xr, yl, yr);
	if (T[no].sum == 0) return;

	if (xr < xu or xl > xv) return;
	if (yr < yu or yl > yv) return;

	if (T[no].l == 0 and T[no].r == 0) {
		for (int it: T[no].a) if (intersect(it, bc)) {
			par[it] = bc;
			rem.emplace_back(it);
			T[no].sum--;
		}

		reverse(all(rem));
		vi& a = T[no].a;
		int j = 0;
		FOR (i, 0, sz(a) - 1) {
			if (rem.empty() or a[i] != rem.back()) {
				a[j] = a[i];
				++j;
			} else {
				rem.pop_back();
			}
		}
		a.resize(j);
		rem.clear();
		return;
	}

	if (dim) {
		int mid = (yl+yr)>>1;
		get(T[no].l, 0, xl,xr,yl, mid);
		get(T[no].r, 0, xl, xr, mid+1, yr);
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	} else {
		int mid = (xl+xr)>>1;
		get(T[no].l, 1, xl, mid, yl, yr);
		get(T[no].r, 1, mid+1, xr, yl, yr);
		T[no].sum = T[T[no].l].sum + T[T[no].r].sum;
	}

}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	x.resize(n), y.resize(n), r.resize(n);
	par = vi(n, -1);

	FOR (i, 0, n - 1) {
		cin >> x[i] >> y[i] >> r[i];
		xc.emplace_back(x[i]);
		yc.emplace_back(y[i]);
	}
	sort(all(xc)); xc.erase(unique(all(xc)), xc.end());
	sort(all(yc)); yc.erase(unique(all(yc)), yc.end());

	vi id(n); iota(all(id), 0);
	sort(all(id), [&](int x, int y) {
		if (r[x] == r[y]) return x < y;
		return r[x] > r[y];
	});

	T.reserve(3e6);

	T.emplace_back();
	int root = build(0, 0, -inf, inf, -inf, inf, id);
	// return 0;

	for (int i : id) if (par[i] == -1) {
			bc = i;
			xu = max(x[i] - 2LL * r[i], (ll) - inf);
			xv = min(x[i] + 2LL * r[i], (ll)inf);

			yu = max(y[i] - 2LL * r[i], (ll) - inf);
			yv = min(y[i] + 2LL * r[i], (ll)inf);

			get(root, 0, -inf, inf, -inf, inf);
		}

	FOR (i, 0, n - 1) cout << par[i] + 1 << " ";



	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	404 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	8 ms	1272 KB	Output is correct
20	Correct	9 ms	1528 KB	Output is correct
21	Correct	9 ms	1272 KB	Output is correct
22	Correct	11 ms	1276 KB	Output is correct
23	Correct	12 ms	1400 KB	Output is correct
24	Correct	10 ms	1272 KB	Output is correct
25	Correct	10 ms	1272 KB	Output is correct
26	Correct	10 ms	1272 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	642 ms	71144 KB	Output is correct
2	Correct	660 ms	77916 KB	Output is correct
3	Correct	668 ms	78684 KB	Output is correct
4	Correct	578 ms	77588 KB	Output is correct
5	Correct	622 ms	76708 KB	Output is correct
6	Correct	929 ms	87028 KB	Output is correct
7	Correct	690 ms	87288 KB	Output is correct
8	Correct	712 ms	89088 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	259 ms	17264 KB	Output is correct
3	Correct	996 ms	52036 KB	Output is correct
4	Correct	1055 ms	59592 KB	Output is correct
5	Correct	900 ms	75100 KB	Output is correct
6	Correct	480 ms	48508 KB	Output is correct
7	Correct	272 ms	28012 KB	Output is correct
8	Correct	56 ms	7416 KB	Output is correct
9	Correct	1034 ms	64652 KB	Output is correct
10	Correct	945 ms	81500 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	745 ms	53336 KB	Output is correct
2	Correct	711 ms	61096 KB	Output is correct
3	Correct	495 ms	62428 KB	Output is correct
4	Correct	656 ms	60096 KB	Output is correct
5	Correct	856 ms	61912 KB	Output is correct
6	Correct	494 ms	61536 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	404 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	8 ms	1272 KB	Output is correct
20	Correct	9 ms	1528 KB	Output is correct
21	Correct	9 ms	1272 KB	Output is correct
22	Correct	11 ms	1276 KB	Output is correct
23	Correct	12 ms	1400 KB	Output is correct
24	Correct	10 ms	1272 KB	Output is correct
25	Correct	10 ms	1272 KB	Output is correct
26	Correct	10 ms	1272 KB	Output is correct
27	Correct	15 ms	2296 KB	Output is correct
28	Correct	15 ms	2280 KB	Output is correct
29	Correct	14 ms	2168 KB	Output is correct
30	Correct	19 ms	2168 KB	Output is correct
31	Correct	20 ms	2296 KB	Output is correct
32	Correct	34 ms	2168 KB	Output is correct
33	Correct	157 ms	17980 KB	Output is correct
34	Correct	157 ms	17900 KB	Output is correct
35	Correct	155 ms	18028 KB	Output is correct
36	Correct	230 ms	18372 KB	Output is correct
37	Correct	235 ms	17784 KB	Output is correct
38	Correct	241 ms	18068 KB	Output is correct
39	Correct	573 ms	19180 KB	Output is correct
40	Correct	792 ms	19176 KB	Output is correct
41	Correct	1507 ms	19052 KB	Output is correct
42	Correct	242 ms	26748 KB	Output is correct
43	Correct	308 ms	23276 KB	Output is correct
44	Correct	302 ms	23328 KB	Output is correct
45	Correct	342 ms	23216 KB	Output is correct
46	Correct	314 ms	23404 KB	Output is correct
47	Correct	308 ms	23276 KB	Output is correct
48	Correct	293 ms	23336 KB	Output is correct
49	Correct	270 ms	23404 KB	Output is correct
50	Correct	354 ms	23404 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	404 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	3 ms	504 KB	Output is correct
17	Correct	3 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct
19	Correct	8 ms	1272 KB	Output is correct
20	Correct	9 ms	1528 KB	Output is correct
21	Correct	9 ms	1272 KB	Output is correct
22	Correct	11 ms	1276 KB	Output is correct
23	Correct	12 ms	1400 KB	Output is correct
24	Correct	10 ms	1272 KB	Output is correct
25	Correct	10 ms	1272 KB	Output is correct
26	Correct	10 ms	1272 KB	Output is correct
27	Correct	642 ms	71144 KB	Output is correct
28	Correct	660 ms	77916 KB	Output is correct
29	Correct	668 ms	78684 KB	Output is correct
30	Correct	578 ms	77588 KB	Output is correct
31	Correct	622 ms	76708 KB	Output is correct
32	Correct	929 ms	87028 KB	Output is correct
33	Correct	690 ms	87288 KB	Output is correct
34	Correct	712 ms	89088 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	259 ms	17264 KB	Output is correct
37	Correct	996 ms	52036 KB	Output is correct
38	Correct	1055 ms	59592 KB	Output is correct
39	Correct	900 ms	75100 KB	Output is correct
40	Correct	480 ms	48508 KB	Output is correct
41	Correct	272 ms	28012 KB	Output is correct
42	Correct	56 ms	7416 KB	Output is correct
43	Correct	1034 ms	64652 KB	Output is correct
44	Correct	945 ms	81500 KB	Output is correct
45	Correct	745 ms	53336 KB	Output is correct
46	Correct	711 ms	61096 KB	Output is correct
47	Correct	495 ms	62428 KB	Output is correct
48	Correct	656 ms	60096 KB	Output is correct
49	Correct	856 ms	61912 KB	Output is correct
50	Correct	494 ms	61536 KB	Output is correct
51	Correct	15 ms	2296 KB	Output is correct
52	Correct	15 ms	2280 KB	Output is correct
53	Correct	14 ms	2168 KB	Output is correct
54	Correct	19 ms	2168 KB	Output is correct
55	Correct	20 ms	2296 KB	Output is correct
56	Correct	34 ms	2168 KB	Output is correct
57	Correct	157 ms	17980 KB	Output is correct
58	Correct	157 ms	17900 KB	Output is correct
59	Correct	155 ms	18028 KB	Output is correct
60	Correct	230 ms	18372 KB	Output is correct
61	Correct	235 ms	17784 KB	Output is correct
62	Correct	241 ms	18068 KB	Output is correct
63	Correct	573 ms	19180 KB	Output is correct
64	Correct	792 ms	19176 KB	Output is correct
65	Correct	1507 ms	19052 KB	Output is correct
66	Correct	242 ms	26748 KB	Output is correct
67	Correct	308 ms	23276 KB	Output is correct
68	Correct	302 ms	23328 KB	Output is correct
69	Correct	342 ms	23216 KB	Output is correct
70	Correct	314 ms	23404 KB	Output is correct
71	Correct	308 ms	23276 KB	Output is correct
72	Correct	293 ms	23336 KB	Output is correct
73	Correct	270 ms	23404 KB	Output is correct
74	Correct	354 ms	23404 KB	Output is correct
75	Correct	543 ms	60764 KB	Output is correct
76	Correct	616 ms	64428 KB	Output is correct
77	Correct	620 ms	66852 KB	Output is correct
78	Correct	531 ms	62292 KB	Output is correct
79	Correct	538 ms	60296 KB	Output is correct
80	Correct	564 ms	60548 KB	Output is correct
81	Correct	843 ms	60996 KB	Output is correct
82	Correct	805 ms	60636 KB	Output is correct
83	Correct	916 ms	61944 KB	Output is correct
84	Correct	1039 ms	62268 KB	Output is correct
85	Correct	940 ms	59868 KB	Output is correct
86	Correct	967 ms	60252 KB	Output is correct
87	Correct	1046 ms	62156 KB	Output is correct
88	Execution timed out	3033 ms	57484 KB	Time limit exceeded
89	Halted	0 ms	0 KB	-

답안 #95385

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0