답안 #49362 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49362	2018-05-27T14:51:09 Z	노영훈(#1273, Diuven)	원 고르기 (APIO18_circle_selection)	C++	7 / 100	1440 ms	33352 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=300010, inf=2e9;

ll sq(int x){
	return 1LL*x*x;
}

struct circle {
	int x, y, r, idx, kill;
	bool operator ^ (const circle &c) const {
		return sq(x-c.x)+sq(y-c.y)<=sq(r+c.r);
	}
} C[MX];

int n;

void solve1(){
	bool out[MX]={};
	for(int _=1; _<=n; _++){
		int now=-1;
		for(int i=1; i<=n; i++){
			if(out[i]) continue;
			if(now<0 || C[now].r<C[i].r) now=i;
		}
		if(now<0) break;
		for(int i=1; i<=n; i++){
			if(out[i]) continue;
			if(C[i]^C[now]) C[i].kill=now, out[i]=true;
		}
	}
	for(int i=1; i<=n; i++) cout<<C[i].kill<<' ';
}

struct line {
	int s, e, r, idx, kill;
} S[MX];

struct node {
	int idx, lz;
} tree[8*MX];

int f(int x, int y){
	if(S[x].r==S[y].r) return min(x,y);
	return S[x].r<S[y].r ? y : x;
}

void busy(int v, int s, int e){
	if(s==e) return;
	node &nd=tree[v];
	node &nd1=tree[v*2], &nd2=tree[v*2+1];
	nd1.lz=f(nd1.lz, nd.lz);
	nd1.idx=f(nd1.idx, nd1.lz);
	nd2.lz=f(nd2.lz, nd.lz);
	nd2.idx=f(nd2.idx, nd2.lz);
}

void upt(int v, int s, int e, int l, int r, int val){
	if(r<s || e<l) return;
	node &nd=tree[v];
	if(l<=s && e<=r){
		nd.lz=f(nd.lz, val);
		nd.idx=f(nd.idx, nd.lz);
		return;
	}
	busy(v,s,e);
	upt(v*2,s,(s+e)/2,l,r,val);
	upt(v*2+1,(s+e)/2+1,e,l,r,val);
	nd.idx=f(tree[v*2].idx, tree[v*2+1].idx);
}

int idx(int v, int s, int e, int l, int r){
	if(r<s || e<l) return 0;
	if(l<=s && e<=r){
		return tree[v].idx;
	}
	busy(v,s,e);
	return f(idx(v*2,s,(s+e)/2,l,r), idx(v*2+1,(s+e)/2+1,e,l,r));
}

void solve2(){
	for(int i=1; i<=n; i++){
		S[i].s=C[i].x-C[i].r;
		S[i].e=C[i].x+C[i].r;
		S[i].r=C[i].r;
		S[i].idx=i;
	}
	vector<int> X;
	for(int i=1; i<=n; i++){
		X.push_back(S[i].s);
		X.push_back(S[i].e);
	}
	sort(X.begin(), X.end());
	int m=unique(X.begin(), X.end())-X.begin();
	X.resize(m);
	for(int i=1; i<=n; i++){
		S[i].s=lower_bound(X.begin(), X.end(), S[i].s)-X.begin()+1;
		S[i].e=lower_bound(X.begin(), X.end(), S[i].e)-X.begin()+1;
	}
	for(int i=1; i<=n; i++){
		upt(1,1,m,S[i].s,S[i].e,i);
	}
	for(int i=1; i<=n; i++){
		cout<<idx(1,1,m,S[i].s,S[i].e)<<' ';
	}
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>C[i].x>>C[i].y>>C[i].r;
		C[i].idx=i;
	}
	if(n<=5000)
		solve1();
	else{
		solve2();
	}
	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	816 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	816 KB	Output is correct
6	Correct	3 ms	816 KB	Output is correct
7	Correct	3 ms	816 KB	Output is correct
8	Correct	2 ms	816 KB	Output is correct
9	Correct	2 ms	816 KB	Output is correct
10	Correct	3 ms	844 KB	Output is correct
11	Correct	2 ms	844 KB	Output is correct
12	Correct	3 ms	844 KB	Output is correct
13	Correct	3 ms	848 KB	Output is correct
14	Correct	2 ms	848 KB	Output is correct
15	Correct	2 ms	848 KB	Output is correct
16	Correct	3 ms	848 KB	Output is correct
17	Correct	4 ms	848 KB	Output is correct
18	Correct	3 ms	848 KB	Output is correct
19	Correct	6 ms	976 KB	Output is correct
20	Correct	5 ms	976 KB	Output is correct
21	Correct	6 ms	992 KB	Output is correct
22	Correct	201 ms	1028 KB	Output is correct
23	Correct	186 ms	1044 KB	Output is correct
24	Correct	190 ms	1068 KB	Output is correct
25	Correct	208 ms	1080 KB	Output is correct
26	Correct	192 ms	1080 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1440 ms	33352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	33352 KB	Output is correct
2	Incorrect	351 ms	33352 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1105 ms	33352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	816 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	816 KB	Output is correct
6	Correct	3 ms	816 KB	Output is correct
7	Correct	3 ms	816 KB	Output is correct
8	Correct	2 ms	816 KB	Output is correct
9	Correct	2 ms	816 KB	Output is correct
10	Correct	3 ms	844 KB	Output is correct
11	Correct	2 ms	844 KB	Output is correct
12	Correct	3 ms	844 KB	Output is correct
13	Correct	3 ms	848 KB	Output is correct
14	Correct	2 ms	848 KB	Output is correct
15	Correct	2 ms	848 KB	Output is correct
16	Correct	3 ms	848 KB	Output is correct
17	Correct	4 ms	848 KB	Output is correct
18	Correct	3 ms	848 KB	Output is correct
19	Correct	6 ms	976 KB	Output is correct
20	Correct	5 ms	976 KB	Output is correct
21	Correct	6 ms	992 KB	Output is correct
22	Correct	201 ms	1028 KB	Output is correct
23	Correct	186 ms	1044 KB	Output is correct
24	Correct	190 ms	1068 KB	Output is correct
25	Correct	208 ms	1080 KB	Output is correct
26	Correct	192 ms	1080 KB	Output is correct
27	Incorrect	28 ms	33352 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	816 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	816 KB	Output is correct
6	Correct	3 ms	816 KB	Output is correct
7	Correct	3 ms	816 KB	Output is correct
8	Correct	2 ms	816 KB	Output is correct
9	Correct	2 ms	816 KB	Output is correct
10	Correct	3 ms	844 KB	Output is correct
11	Correct	2 ms	844 KB	Output is correct
12	Correct	3 ms	844 KB	Output is correct
13	Correct	3 ms	848 KB	Output is correct
14	Correct	2 ms	848 KB	Output is correct
15	Correct	2 ms	848 KB	Output is correct
16	Correct	3 ms	848 KB	Output is correct
17	Correct	4 ms	848 KB	Output is correct
18	Correct	3 ms	848 KB	Output is correct
19	Correct	6 ms	976 KB	Output is correct
20	Correct	5 ms	976 KB	Output is correct
21	Correct	6 ms	992 KB	Output is correct
22	Correct	201 ms	1028 KB	Output is correct
23	Correct	186 ms	1044 KB	Output is correct
24	Correct	190 ms	1068 KB	Output is correct
25	Correct	208 ms	1080 KB	Output is correct
26	Correct	192 ms	1080 KB	Output is correct
27	Incorrect	1440 ms	33352 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

답안 #49362

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0