Submission #1087893

#TimeUsernameProblemLanguageResultExecution timeMemory
1087893alexander707070Circle selection (APIO18_circle_selection)C++14
0 / 100
647 ms58548 KiB
#include<bits/stdc++.h> #define MAXN 600007 using namespace std; int n,par[MAXN],cnt; long long x[MAXN],y[MAXN],r[MAXN]; pair<int,int> p[MAXN]; map<int,int> mp; vector<int> w; int tree[4*MAXN]; void update(int v,int l,int r,int ll,int rr,int val){ if(ll>rr)return; if(l==ll and r==rr){ tree[v]=val; }else{ int tt=(l+r)/2; if(tree[v]!=0){ tree[2*v]=tree[2*v+1]=tree[v]; tree[v]=0; } update(2*v,l,tt,ll,min(tt,rr),val); update(2*v+1,tt+1,r,max(tt+1,ll),rr,val); } } int getpos(int v,int l,int r,int pos){ if(l==r)return tree[v]; int tt=(l+r)/2; if(tree[v]!=0){ tree[2*v]=tree[2*v+1]=tree[v]; tree[v]=0; } if(pos<=tt)return getpos(2*v,l,tt,pos); return getpos(2*v+1,tt+1,r,pos); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]>>r[i]; w.push_back(x[i]-r[i]); w.push_back(x[i]+r[i]); p[i]={r[i],-i}; } sort(w.begin(),w.end()); for(int i=0;i<w.size();i++){ if(i==0 or w[i]!=w[i-1])cnt++; mp[w[i]]=cnt; } sort(p+1,p+n+1); for(int i=n;i>=1;i--){ int curr=-p[i].second; int e=getpos(1,1,cnt,mp[x[curr]-r[curr]]); if(e!=0){ par[curr]=e; continue; } e=getpos(1,1,cnt,mp[x[curr]+r[curr]]); if(e!=0){ par[curr]=e; continue; } par[curr]=curr; update(1,1,cnt,mp[x[curr]-r[curr]],mp[x[curr]+r[curr]],curr); } for(int i=1;i<=n;i++){ cout<<par[i]<<" "; } cout<<"\n"; return 0; }

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<w.size();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...