oj.uz

Submission #304010

# Submission time Handle Problem Language Result Execution time Memory
304010 2020-09-21T00:03:51 Z arnold518 Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 533164 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 6e5;
 
struct Circle
{
	ll x, y, r; int p;
};
 
int N;
Circle A[MAXN+10], B[MAXN+10];
vector<ll> xcomp, ycomp;
bool vis[MAXN+10];
 
int getycomp(int x) { return lower_bound(ycomp.begin(), ycomp.end(), x)-ycomp.begin()+1; }
 
struct SEG
{
	multimap<ll, int> tree[MAXN*4+10];
	void push(int node, int tl, int tr, int pos, ll p, int q)
	{
		tree[node].insert({p, q});
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(pos<=mid) push(node*2, tl, mid, pos, p, q);
		else push(node*2+1, mid+1, tr, pos, p, q);
	}
	void pop(int node, int tl, int tr, int l, int r, ll pl, ll pr, vector<int> &V)
	{
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			vector<map<ll, int>::iterator> del;
			for(auto it=tree[node].lower_bound(pl); it!=tree[node].upper_bound(pr); it++)
			{
				if(vis[it->second]) { del.push_back(it); continue; }
				V.push_back(it->second);
			}
			for(auto it : del) tree[node].erase(it);
			return;
		}
		int mid=tl+tr>>1;
		pop(node*2, tl, mid, l, r, pl, pr, V);
		pop(node*2+1, mid+1, tr, l, r, pl, pr, V);
	}
}seg;
 
int ans[MAXN+10];
 
int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r), A[i].p=i;
	for(int i=1; i<=N; i++) B[i]=A[i];
	sort(A+1, A+N+1, [&](const Circle &p, const Circle &q)
	{
		if(p.r!=q.r) return p.r>q.r;
		return p.p<q.p;
	});

	for(int i=1; i<=N; i++)
	{
		xcomp.push_back(A[i].x-A[i].r);
		xcomp.push_back(A[i].x+A[i].r);
		ycomp.push_back(A[i].y-A[i].r);
		ycomp.push_back(A[i].y+A[i].r);
	}
	
	sort(xcomp.begin(), xcomp.end());
	xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
	
	sort(ycomp.begin(), ycomp.end());
	ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
	
	for(int i=1; i<=N; i++)
	{
		int l=getycomp(A[i].y-A[i].r), r=getycomp(A[i].y+A[i].r);
		seg.push(1, 1, ycomp.size(), l, A[i].x-A[i].r, A[i].p);
		seg.push(1, 1, ycomp.size(), l, A[i].x+A[i].r, A[i].p);
		seg.push(1, 1, ycomp.size(), r, A[i].x-A[i].r, A[i].p);
		seg.push(1, 1, ycomp.size(), r, A[i].x+A[i].r, A[i].p);
	}

	for(int i=1; i<=N; i++)
	{
		if(vis[A[i].p]) continue;
		ans[A[i].p]=A[i].p;
		vis[A[i].p]=1;
		vector<int> V;
		int l=getycomp(A[i].y-A[i].r), r=getycomp(A[i].y+A[i].r);
		seg.pop(1, 1, ycomp.size(), l, r, A[i].x-A[i].r, A[i].x+A[i].r, V);
		sort(V.begin(), V.end());
		V.erase(unique(V.begin(), V.end()), V.end());
		for(auto it : V)
		{
			if((A[i].x-B[it].x)*(A[i].x-B[it].x)+(A[i].y-B[it].y)*(A[i].y-B[it].y)>(A[i].r+B[it].r)*(A[i].r+B[it].r)) continue;
			ans[it]=A[i].p;
			vis[it]=1;
		}
	}
	for(int i=1; i<=N; i++) printf("%d ", ans[i]);
}

Compilation message

circle_selection.cpp: In member function 'void SEG::push(int, int, int, int, ll, int)':
circle_selection.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In member function 'void SEG::pop(int, int, int, int, int, ll, ll, std::vector<int>&)':
circle_selection.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113144 KB Output is correct
3 Correct 74 ms 113148 KB Output is correct
4 Correct 73 ms 113016 KB Output is correct
5 Correct 73 ms 113020 KB Output is correct
6 Correct 74 ms 113272 KB Output is correct
7 Correct 73 ms 113272 KB Output is correct
8 Correct 75 ms 113272 KB Output is correct
9 Correct 75 ms 113272 KB Output is correct
10 Correct 74 ms 113272 KB Output is correct
11 Correct 74 ms 113272 KB Output is correct
12 Correct 73 ms 113272 KB Output is correct
13 Correct 74 ms 113272 KB Output is correct
14 Correct 76 ms 113272 KB Output is correct
15 Correct 73 ms 113240 KB Output is correct
16 Correct 85 ms 116216 KB Output is correct
17 Correct 88 ms 116344 KB Output is correct
18 Correct 85 ms 116216 KB Output is correct
19 Correct 201 ms 131960 KB Output is correct
20 Correct 191 ms 131960 KB Output is correct
21 Correct 218 ms 131960 KB Output is correct
22 Correct 202 ms 131752 KB Output is correct
23 Correct 216 ms 131880 KB Output is correct
24 Correct 210 ms 131832 KB Output is correct
25 Correct 207 ms 131704 KB Output is correct
26 Correct 212 ms 131832 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 484676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 113144 KB Output is correct
2 Execution timed out 3407 ms 500420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3171 ms 533164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113144 KB Output is correct
3 Correct 74 ms 113148 KB Output is correct
4 Correct 73 ms 113016 KB Output is correct
5 Correct 73 ms 113020 KB Output is correct
6 Correct 74 ms 113272 KB Output is correct
7 Correct 73 ms 113272 KB Output is correct
8 Correct 75 ms 113272 KB Output is correct
9 Correct 75 ms 113272 KB Output is correct
10 Correct 74 ms 113272 KB Output is correct
11 Correct 74 ms 113272 KB Output is correct
12 Correct 73 ms 113272 KB Output is correct
13 Correct 74 ms 113272 KB Output is correct
14 Correct 76 ms 113272 KB Output is correct
15 Correct 73 ms 113240 KB Output is correct
16 Correct 85 ms 116216 KB Output is correct
17 Correct 88 ms 116344 KB Output is correct
18 Correct 85 ms 116216 KB Output is correct
19 Correct 201 ms 131960 KB Output is correct
20 Correct 191 ms 131960 KB Output is correct
21 Correct 218 ms 131960 KB Output is correct
22 Correct 202 ms 131752 KB Output is correct
23 Correct 216 ms 131880 KB Output is correct
24 Correct 210 ms 131832 KB Output is correct
25 Correct 207 ms 131704 KB Output is correct
26 Correct 212 ms 131832 KB Output is correct
27 Correct 397 ms 153204 KB Output is correct
28 Correct 370 ms 153096 KB Output is correct
29 Correct 390 ms 153208 KB Output is correct
30 Correct 341 ms 152820 KB Output is correct
31 Correct 345 ms 152948 KB Output is correct
32 Correct 333 ms 152988 KB Output is correct
33 Execution timed out 3130 ms 459356 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113144 KB Output is correct
3 Correct 74 ms 113148 KB Output is correct
4 Correct 73 ms 113016 KB Output is correct
5 Correct 73 ms 113020 KB Output is correct
6 Correct 74 ms 113272 KB Output is correct
7 Correct 73 ms 113272 KB Output is correct
8 Correct 75 ms 113272 KB Output is correct
9 Correct 75 ms 113272 KB Output is correct
10 Correct 74 ms 113272 KB Output is correct
11 Correct 74 ms 113272 KB Output is correct
12 Correct 73 ms 113272 KB Output is correct
13 Correct 74 ms 113272 KB Output is correct
14 Correct 76 ms 113272 KB Output is correct
15 Correct 73 ms 113240 KB Output is correct
16 Correct 85 ms 116216 KB Output is correct
17 Correct 88 ms 116344 KB Output is correct
18 Correct 85 ms 116216 KB Output is correct
19 Correct 201 ms 131960 KB Output is correct
20 Correct 191 ms 131960 KB Output is correct
21 Correct 218 ms 131960 KB Output is correct
22 Correct 202 ms 131752 KB Output is correct
23 Correct 216 ms 131880 KB Output is correct
24 Correct 210 ms 131832 KB Output is correct
25 Correct 207 ms 131704 KB Output is correct
26 Correct 212 ms 131832 KB Output is correct
27 Execution timed out 3066 ms 484676 KB Time limit exceeded
28 Halted 0 ms 0 KB -