oj.uz

Submission #303351

# Submission time Handle Problem Language Result Execution time Memory
303351 2020-09-20T08:46:49 Z arnold518 Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 1048580 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];
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(tr); 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;
	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-A[it].x)*(A[i].x-A[it].x)+(A[i].y-A[it].y)*(A[i].y-A[it].y)>(A[i].r+A[it].r)*(A[i].r+A[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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 113016 KB Output is correct
2 Correct 75 ms 113144 KB Output is correct
3 Incorrect 74 ms 113020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2642 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 113016 KB Output is correct
2 Correct 75 ms 113144 KB Output is correct
3 Incorrect 74 ms 113020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 113016 KB Output is correct
2 Correct 75 ms 113144 KB Output is correct
3 Incorrect 74 ms 113020 KB Output isn't correct
4 Halted 0 ms 0 KB -