Submission #304012

#TimeUsernameProblemLanguageResultExecution timeMemory
304012arnold518Circle selection (APIO18_circle_selection)C++14
37 / 100
3140 ms901448 KiB
#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 Node { ll x, y; int par; Node(int x, int y) : x(x), y(y), par(0) {} bool operator < (const Node &p) { return x<p.x; } }; int Find(int x, vector<Node> &V) { if(x>=V.size()) return x; if(V[x].par==x) return x; return V[x].par=Find(V[x].par, V); } struct SEG { vector<Node> tree[MAXN*4+10]; void push(int node, int tl, int tr, int pos, ll p, int q) { tree[node].push_back(Node(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 init(int node, int tl, int tr) { sort(tree[node].begin(), tree[node].end()); for(int i=0; i<tree[node].size(); i++) tree[node][i].par=i; if(tl==tr) return; int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); } 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) { for(int i=Find(lower_bound(tree[node].begin(), tree[node].end(), Node(pl, 0))-tree[node].begin(), tree[node]); i<tree[node].size() && tree[node][i].x<=pr; i=Find(i+1, tree[node])) { if(vis[tree[node][i].y]) { int t=Find(i+1, tree[node]); tree[node][i].par=t; } else { V.push_back(tree[node][i].y); } } 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); } seg.init(1, 1, ycomp.size()); 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 (stderr)

circle_selection.cpp: In function 'int Find(int, std::vector<Node>&)':
circle_selection.cpp:32:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if(x>=V.size()) return x;
      |     ~^~~~~~~~~~
circle_selection.cpp: In member function 'void SEG::push(int, int, int, int, ll, int)':
circle_selection.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In member function 'void SEG::init(int, int, int)':
circle_selection.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0; i<tree[node].size(); i++) tree[node][i].par=i;
      |                ~^~~~~~~~~~~~~~~~~~
circle_selection.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   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:62:116: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for(int i=Find(lower_bound(tree[node].begin(), tree[node].end(), Node(pl, 0))-tree[node].begin(), tree[node]); i<tree[node].size() && tree[node][i].x<=pr; i=Find(i+1, tree[node]))
      |                                                                                                                   ~^~~~~~~~~~~~~~~~~~
circle_selection.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:87:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |  for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...