Submission #318508

#TimeUsernameProblemLanguageResultExecution timeMemory
318508IloveNCircle selection (APIO18_circle_selection)C++14
0 / 100
581 ms1048580 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back #define all(vr) vr.begin(),vr.end() #define vi vector<int> #define vll vector<ll> const int N=3e5+10; const ll inf=1e9; struct circle{int x,y,r,id;}; circle a[N]; int n; struct segment_tree_2d { vi pre[N*4],nex[N*4],pos_in[N]; vector<char> it[N*4]; vector<pii> val[N*4]; pii arr[N]; int len; void build(int id,int l,int r) { if (l==r) { val[id].eb(arr[l]); it[id].resize(5,1); pre[id].eb(-1); nex[id].eb(2); pos_in[l].eb(0); return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); val[id].resize(val[id*2].size()+val[id*2+1].size()); merge(all(val[id*2]),all(val[id*2+1]),val[id].begin()); pre[id].resize(val[id].size()); nex[id].resize(val[id].size()); for (int i=0;i<(int)val[id].size();i++) pre[id][i]=i-1,nex[id][i]=i+1,pos_in[val[id][i].se].eb(i); it[id].resize(val[id].size()*4+1,1); } void input(pii ar[],int siz) { len=siz; for (int i=1;i<=len;i++) arr[i]=ar[i]; build(1,1,len); } void update_sub(int sub,int id,int l,int r,int v) { if (l==r) { it[sub][id]=0; return; } int mid=(l+r)/2; if (v<=mid) update_sub(sub,id*2,l,mid,v); else update_sub(sub,id*2+1,mid+1,r,v); it[sub][id]=(it[sub][id*2] | it[sub][id*2+1]); } void update(int id,int l,int r,int v,int layer) { int pos=pos_in[v][layer]; update_sub(id,1,1,val[id].size(),pos+1); if (pre[id][pos]>-1) nex[id][pre[id][pos]]=nex[id][pos]; if (nex[id][pos]<(int)val[id].size()) pre[id][nex[id][pos]]=pre[id][pos]; if (l==r) return; int mid=(l+r)/2; if (v<=mid) update(id*2,l,mid,v,layer-1); else update(id*2+1,mid+1,r,v,layer-1); } int lw_sub(int sub,int id,int l,int r,int v) { if (r<v || !it[sub][id]) return 0; if (l==r) return l; int mid=(l+r)/2; int res=lw_sub(sub,id*2,l,mid,v); if (res) return res; return lw_sub(sub,id*2+1,mid+1,r,v); } vi pot; void searc(int id,int l,int r,int u,int v,int y1,int y2) { if (l>v || r<u) return; if (u<=l && r<=v) { int pos=lower_bound(all(val[id]),mp(y1,0))-val[id].begin()+1; pos=lw_sub(id,1,1,val[id].size(),pos)-1; if (pos<0) return; while (pos<(int)val[id].size() && val[id][pos].fi<=y2) { pot.eb(val[id][pos].se); pos=nex[id][pos]; } return; } int mid=(l+r)/2; searc(id*2,l,mid,u,v,y1,y2); searc(id*2+1,mid+1,r,u,v,y1,y2); } vi find_pot(int u,int v,int y1,int y2) { pot.clear(); if (u<=v) searc(1,1,n,u,v,y1,y2); return pot; } void del(vi &vt) { for (int x : vt) update(1,1,n,x,pos_in[x].size()-1); } } seg; void read() { cin>>n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].r),a[i].id=i; } bool cmp(circle &obj1, circle &obj2) { return (obj1.r>obj2.r) || ((obj1.r==obj2.r) && (obj1.id<obj2.id));} pii X[N],Y[N]; int ans[N]; ll sqr(ll x) { return x*x;} bool intersect(int i,int j) { return sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)<=sqr(a[i].r+a[j].r); } void process() { sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++) X[i]=mp(a[i].x,i); sort(X+1,X+n+1); for (int i=1;i<=n;i++) Y[i]=mp(a[X[i].se].y,i); seg.input(Y,n); for (int i=1;i<=n;i++) if (ans[a[i].id]==0) { int x1=max(-inf,(ll)a[i].x-a[i].r*2),x2=min(inf,(ll)a[i].x+a[i].r*2); int y1=max(-inf,(ll)a[i].y-a[i].r*2),y2=min(inf,(ll)a[i].y+a[i].r*2); int u=lower_bound(X+1,X+n+1,mp(x1,0))-X; int v=upper_bound(X+1,X+n+1,mp(x2,n+2))-X-1; vi vt=seg.find_pot(u,v,y1,y2); vi vt2; for (int x : vt) if (intersect(i,X[x].se)) ans[a[X[x].se].id]=a[i].id,vt2.eb(x); seg.del(vt2); } for (int i=1;i<=n;i++) cout<<ans[i]<<" "; } int main() { //freopen("ss.inp","r",stdin); ios::sync_with_stdio(false); cout.tie(0); read(); process(); return 0; }

Compilation message (stderr)

circle_selection.cpp: In function 'void read()':
circle_selection.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:133:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |     for (int i=1;i<=n;i++) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].r),a[i].id=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...