Submission #272709

#TimeUsernameProblemLanguageResultExecution timeMemory
272709MKopchevCircle selection (APIO18_circle_selection)C++14
87 / 100
3101 ms395608 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=3e5+42,inf=1e9+42; struct circle { int x,y,r,id; }; int n; circle inp[nmax],sorted_inp[nmax]; bool touch(circle a,circle b) { long long d=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y); long long mx=a.r+b.r; mx=mx*mx; return d<=mx; } bool cmp(circle a,circle b) { if(a.r!=b.r)return a.r>b.r; return a.id<b.id; } int outp[nmax]; vector< pair<int/*y*/,int/*id*/> > nodes[nmax*4]; vector<int> prv[nmax*4]; vector<int> nxt[nmax*4]; vector<int> tree[nmax*4]; void update(int node,int l,int r,int pos,circle cur) { //cout<<node<<" -> "<<cur.y<<" "<<cur.id<<endl; nodes[node].push_back({cur.y,cur.id}); if(l==r)return; int av=(l+r)/2; if(pos<=av)update(node*2,l,av,pos,cur); else update(node*2+1,av+1,r,pos,cur); } void build(int where,int node,int l,int r) { while(tree[where].size()<=node)tree[where].push_back(0); tree[where][node]=r-l+1; if(l==r)return; int av=(l+r)/2; build(where,node*2,l,av); build(where,node*2+1,av+1,r); } void sub_tree(int where,int node,int l,int r,int pos) { tree[where][node]--; if(l==r)return; int av=(l+r)/2; if(pos<=av)sub_tree(where,node*2,l,av,pos); else sub_tree(where,node*2+1,av+1,r,pos); } int query(int where,int node,int l,int r,int lq,int rq) { if(tree[where][node]==0)return -1; if(l==r)return l; int av=(l+r)/2; if(lq<=av) { int mem=query(where,node*2,l,av,lq,min(av,rq)); if(mem!=-1)return mem; } if(av<rq) { int mem=query(where,node*2+1,av+1,r,max(av+1,lq),rq); if(mem!=-1)return mem; } return -1; } int find_first(int where,int start) { return query(where,1,0,nodes[where].size()-1,start,nodes[where].size()-1); } int pick(int a,int b) { long long sum=a; sum=sum+b; if(inf<sum)sum=inf; if(-inf>sum)sum=-inf; return sum; } void match(int node,int l,int r,int lq,int rq,circle cur) { if(tree[node].size()==0)return; if(tree[node][1]==0)return; if(l==lq&&r==rq) { int y1=pick(cur.y,-2*cur.r); int y2=pick(cur.y,2*cur.r); int start=lower_bound(nodes[node].begin(),nodes[node].end(),make_pair(y1,0))-nodes[node].begin(); if(start==nodes[node].size())return; start=find_first(node,start); /* cout<<"circle "<<l<<" "<<r<<" "<<cur.id<<endl; for(auto k:nodes[node]) cout<<k.first<<" "<<k.second<<"\t";cout<<endl; cout<<"y1= "<<y1<<" y2= "<<y2<<" start= "<<start<<endl; */ if(start==-1)return; vector<int> to_pop={}; while(start<nodes[node].size()&&nodes[node][start].first<=y2) { //cout<<"start= "<<start<<" "<<nodes[node][start].second<<" "<<inp[nodes[node][start].second].x<<" "<<inp[nodes[node][start].second].y<<" "<<inp[nodes[node][start].second].r<<endl; if(outp[nodes[node][start].second]==0&&touch(inp[nodes[node][start].second],cur)) { //cout<<"touch "<<nodes[node][start].second<<" "<<cur.id<<" "<<endl; outp[nodes[node][start].second]=cur.id; } if(outp[nodes[node][start].second])to_pop.push_back(start); start=nxt[node][start]; } for(auto k:to_pop) { if(0<=prv[node][k]) { nxt[node][prv[node][k]]=nxt[node][k]; } if(nxt[node][k]<nodes[node].size()) { prv[node][nxt[node][k]]=prv[node][k]; } sub_tree(node,1,0,nodes[node].size()-1,k); } return; } int av=(l+r)/2; if(lq<=av)match(node*2,l,av,lq,min(av,rq),cur); if(av<rq)match(node*2+1,av+1,r,max(av+1,lq),rq,cur); } int help_x[nmax]; void push(int which) { outp[sorted_inp[which].id]=sorted_inp[which].id; int x1=pick(sorted_inp[which].x,-2*sorted_inp[which].r); int x2=pick(sorted_inp[which].x,+2*sorted_inp[which].r); int le=lower_bound(help_x+1,help_x+n+1,x1)-help_x; int ri=upper_bound(help_x+1,help_x+n+1,x2)-help_x; ri--; //cout<<"le= "<<le<<" ri= "<<ri<<endl; if(le>ri)return; match(1,1,n,le,ri,sorted_inp[which]); } signed main() { scanf("%i",&n); for(int i=1;i<=n;i++) { scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r); inp[i].id=i; } for(int i=1;i<=n;i++)sorted_inp[i]=inp[i]; sort(sorted_inp+1,sorted_inp+n+1,cmp); for(int i=1;i<=n;i++)help_x[i]=sorted_inp[i].x; sort(help_x+1,help_x+n+1); for(int i=1;i<=n;i++) { int pos=lower_bound(help_x+1,help_x+n+1,sorted_inp[i].x)-help_x; update(1,1,n,pos,sorted_inp[i]); } for(int i=1;i<=4*n;i++) if(nodes[i].size()) { sort(nodes[i].begin(),nodes[i].end()); for(int j=0;j<nodes[i].size();j++) { prv[i].push_back(j-1); nxt[i].push_back(j+1); } build(i,1,0,nodes[i].size()-1); } for(int i=1;i<=n;i++) if(outp[sorted_inp[i].id]==0) push(i); for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n"); return 0; }

Compilation message (stderr)

circle_selection.cpp: In function 'void build(int, int, int, int)':
circle_selection.cpp:51:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while(tree[where].size()<=node)tree[where].push_back(0);
      |           ~~~~~~~~~~~~~~~~~~^~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:120:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:157:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:221:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:233:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  233 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:233:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  233 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:195:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  198 |         scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...