Submission #272751

#TimeUsernameProblemLanguageResultExecution timeMemory
272751MKopchevCircle selection (APIO18_circle_selection)C++14
87 / 100
3071 ms373508 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=3e5+42,inf=1e9+42,MX=(1<<20)+42; struct circle { int x,y,r,id; }; int n; circle inp[nmax],sorted_inp[nmax],other_sorted[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; } bool cmp_y(circle a,circle b) { if(a.y!=b.y)return a.y<b.y; return a.id<b.id; } int outp[nmax]; vector< pair<int/*y*/,int/*id*/> > nodes[MX]; vector<int> prv[MX]; vector<int> nxt[MX]; vector<int> fenwick[MX]; 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); } int SZ[nmax]; void upd(int where,int j,int val) { j++; while(j<=SZ[nodes[where].size()]) { fenwick[where][j]+=val; j=j+(j&(-j)); } } void build(int where) { for(int i=0;i<=SZ[nodes[where].size()];i++)fenwick[where].push_back(0); //cout<<where<<" -> "<<fenwick[where].size()<<endl; for(int i=0;i<nodes[where].size();i++) { upd(where,i,1); } //for(int i=1;i<=nodes[where].size();i++)cout<<fenwick[where][i]<<" ";cout<<endl; } void sub_tree(int where,int pos) { upd(where,pos,-1); } int query(int where,int pos) { pos++; int ret=0; while(pos) { ret=ret+fenwick[where][pos]; pos=pos-(pos&(-pos)); } return ret; } int bits[nmax]; int find_first(int where,int start) { int sum=query(where,start-1); //cout<<"find_first "<<where<<" "<<start<<" "<<sum<<endl; if(sum==fenwick[where][SZ[nodes[where].size()]])return -1; int pos=0; for(int j=bits[nodes[where].size()]-1;j>=0;j--) if(fenwick[where][pos+(1<<j)]<=sum) { sum=sum-fenwick[where][pos+(1<<j)]; pos=pos+(1<<j); } //cout<<"pos= "<<pos<<endl; return pos; } 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(fenwick[node].size()==0)return; if(fenwick[node][SZ[nodes[node].size()]]==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,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],other_sorted[i]=inp[i]; sort(other_sorted+1,other_sorted+n+1,cmp_y); 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,other_sorted[i].x)-help_x; update(1,1,n,pos,other_sorted[i]); } int st=0; for(int i=1;i<=n;i++) { if((1<<st)<i)st++; SZ[i]=1<<st; bits[i]=st; //cout<<i<<" -> "<<SZ[i]<<" "<<bits[i]<<endl; } for(int i=1;i<MX;i++) if(nodes[i].size()) { for(int j=0;j<nodes[i].size();j++) { prv[i].push_back(j-1); nxt[i].push_back(j+1); } build(i); } 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)':
circle_selection.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<nodes[where].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:147: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]
  147 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:162: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]
  162 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:184: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]
  184 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:260: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]
  260 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:272:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  272 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:272:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  272 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:222:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  222 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:225:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  225 |         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...