제출 #421159

#제출 시각아이디문제언어결과실행 시간메모리
421159PyqeIzvanzemaljci (COI21_izvanzemaljci)C++14
68 / 100
3063 ms25416 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define fr first #define sc second const long long ma=1e9,inf=1e18; long long n,d,nn,nm[2],sk[2][100069]; pair<long long,long long> a[4][100069],as[4][100069],a2[100069]; pair<long long,array<long long,2>> rg[100069]; pair<pair<long long,long long>,long long> ca[3],sq[3]; bitset<100069> vtd; array<long long,2> a0={-inf,-inf}; struct segtree { long long l,r,lz; pair<long long,long long> mxe; segtree *p[2]; void bd(long long lh,long long rh) { l=lh; r=rh; if(l<r) { long long ii,md=(l+r)/2; for(ii=0;ii<2;ii++) { p[ii]=new segtree; p[ii]->bd(!ii?l:md+1,!ii?md:r); } } } void rst() { lz=0; if(l==r) { mxe={-rg[l-1].fr-1,l}; } else { long long ii; for(ii=0;ii<2;ii++) { p[ii]->rst(); } mxe=max(p[0]->mxe,p[1]->mxe); } } void blc() { long long ii; for(ii=0;ii<2;ii++) { p[ii]->mxe.fr+=lz; p[ii]->lz+=lz; } lz=0; } void ud(long long lh,long long rh,long long w) { if(l>rh||r<lh); else if(l>=lh&&r<=rh) { mxe.fr+=w; lz+=w; } else { long long ii; blc(); for(ii=0;ii<2;ii++) { p[ii]->ud(lh,rh,w); } mxe=max(p[0]->mxe,p[1]->mxe); } } pair<long long,long long> qr(long long lh,long long rh) { if(l>rh||r<lh) { return {-inf,-1}; } else if(l>=lh&&r<=rh) { return mxe; } else { blc(); return max(p[0]->qr(lh,rh),p[1]->qr(lh,rh)); } } } sg; int main() { long long i,j,ii,im,u,x,y,x2,y2,k,l,w,p,mn,mx,mn2,lb,rb,lh,rh,md,c=0; pair<long long,long long> tmp; bool bad; scanf("%lld%lld",&n,&d); for(i=1;i<=n;i++) { scanf("%lld%lld",&x,&y); a[0][i]={x,y}; } for(im=0;im<4;im++) { sort(a[im]+1,a[im]+n+1); for(i=1;i<=n;i++) { as[im][i]={a[im][i].sc,i}; } sort(as[im]+1,as[im]+n+1); if(im<3) { for(i=1;i<=n;i++) { x=a[im][i].fr; y=a[im][i].sc; a[im+1][i]={y,-x}; } } } sg.bd(1,n); for(lh=1,rh=ma*2;lh<=rh;) { md=(lh+rh)/2; bad=0; for(im=0;im<4;im++) { if(d==1) { if(!im) { mn=inf; mx=-inf; mn2=inf; for(i=1;i<=n;i++) { x=a[im][i].fr; y=a[im][i].sc; mn=min(mn,y); mx=max(mx,y); if(mx-mn>md||x-a[im][1].fr>md) { break; } mn2=mn; } if(i>n) { bad=1; sq[0]={{a[im][1].fr,mn2},md}; } } } else if(d==2) { if(im<2) { l=0; for(ii=0;ii<2;ii++) { mn=inf; mx=-inf; k=l; mn2=inf; for(i=l+1;i<=n;i++) { x=a[im][i].fr; y=a[im][i].sc; mn=min(mn,y); mx=max(mx,y); if(mx-mn>md||x-a[im][l+1].fr>md) { break; } if(i==n||x!=a[im][i+1].fr) { k=i; mn2=mn; } } if(!ii) { ca[ii]={{a[im][k].fr-md,mn2},md}; } else { ca[ii]={{a[im][l+1].fr,mn2},md}; } l=k; } if(i>n) { bad=1; for(j=0;j<d;j++) { sq[j]=ca[j]; } } } } else { mn=inf; mx=-inf; k=0; mn2=inf; vtd.reset(); for(i=1;i<=n;i++) { p=as[im][i].sc; x=a[im][p].fr; y=a[im][p].sc; mn=min(mn,x); mx=max(mx,x); if(mx-mn>md||y-as[im][1].fr>md) { break; } if(i==n||y!=as[im][i+1].fr) { mn2=mn; for(;k<i;) { k++; vtd[as[im][k].sc]=1; } } } ca[0]={{mn2,as[im][k].fr-md},md}; nn=0; for(i=1;i<=n;i++) { if(!vtd[i]) { nn++; a2[nn]=a[im][i]; } } l=0; for(ii=0;ii<2;ii++) { mn=inf; mx=-inf; k=l; mn2=inf; for(i=l+1;i<=nn;i++) { x=a2[i].fr; y=a2[i].sc; mn=min(mn,y); mx=max(mx,y); if(mx-mn>md||x-a2[l+1].fr>md) { break; } if(i==nn||x!=a2[i+1].fr) { k=i; mn2=mn; } } if(!ii) { ca[ii+1]={{a2[k].fr-md,mn2},md}; } else { ca[ii+1]={{a2[l+1].fr,mn2},md}; } l=k; } if(i>nn) { bad=1; for(j=0;j<d;j++) { sq[j]=ca[j]; } } if(im<2) { nn=0; rg[0].fr=-ma*4; for(i=1;i<=n;i++) { x=a[im][i].fr; y=a[im][i].sc; if(!nn||x!=rg[nn].fr) { nn++; rg[nn]={x,{y,y}}; } else { rg[nn].sc[0]=min(rg[nn].sc[0],y); rg[nn].sc[1]=max(rg[nn].sc[1],y); } } rg[nn+1].fr=ma*4; mn=inf; mx=-inf; for(i=1;i<=nn;i++) { x=rg[i].fr; y=rg[i].sc[0]; y2=rg[i].sc[1]; mn=min(mn,y); mx=max(mx,y2); if(mx-mn>md||x-rg[1].fr>md) { break; } } lb=i-1; mn=inf; mx=-inf; for(i=nn;i;i--) { x=rg[i].fr; y=rg[i].sc[0]; y2=rg[i].sc[1]; mn=min(mn,y); mx=max(mx,y2); if(mx-mn>md||rg[nn].fr-x>md) { break; } } rb=i+1; sg.rst(); for(ii=0;ii<2;ii++) { nm[ii]=0; } for(i=1;i<=nn;i++) { x=rg[i].fr; y=rg[i].sc[0]; y2=rg[i].sc[1]; for(ii=0;ii<2;ii++) { u=!ii*2-1; for(;nm[ii]&&rg[sk[ii][nm[ii]]].sc[ii]*u>=y*u;nm[ii]--) { sg.ud(sk[ii][nm[ii]-1]+1,sk[ii][nm[ii]],-abs(y-rg[sk[ii][nm[ii]]].sc[ii])); } nm[ii]++; sk[ii][nm[ii]]=i; swap(y,y2); } sg.ud(i,i,y-y2); if(i+1>=rb) { x2=min(rg[i+1].fr-1,x+md); k=lower_bound(rg+1,rg+nn+1,mp(x2-md,a0))-rg; l=upper_bound(rg+1,rg+nn+1,mp(x2-1,a0))-rg-1; tmp=sg.qr(k+1,min(l,lb+1)); if(x2+tmp.fr>=0) { lb=tmp.sc-1; rb=i+1; break; } if(lb+1<=k&&rg[lb+1].fr>=x-md&&md+sg.qr(lb+1,lb+1).fr+rg[lb].fr+1>=0) { rb=i+1; break; } } } if(i<=nn) { bad=1; mn=inf; for(i=1;i<=lb;i++) { x=rg[i].fr; y=rg[i].sc[0]; mn=min(mn,y); } sq[0]={{x-md,mn},md}; mn=inf; for(i=nn;i>=rb;i--) { x=rg[i].fr; y=rg[i].sc[0]; mn=min(mn,y); } sq[1]={{x,mn},md}; mn=inf; for(i=lb+1;i<rb;i++) { y=rg[i].sc[0]; mn=min(mn,y); } x=rg[lb].fr+1; x2=rg[rb].fr-1; if(x2-x>md) { w=min(x2-x-md,x2-rg[rb-1].fr); x2-=w; w=min(x2-x-md,rg[lb+1].fr-x); x+=w; } sq[2]={{x,mn},x2-x}; } } } for(i=0;i<d;i++) { x=sq[i].fr.fr; y=sq[i].fr.sc; w=sq[i].sc; sq[i].fr={y,-x-w}; } } if(bad) { rh=md-1; } else { lh=md+1; } } for(i=0;i<d;i++) { x=sq[i].fr.fr; y=sq[i].fr.sc; w=sq[i].sc; if(x<-ma*3||y<-ma*3||x>ma*3||y>ma*3) { x=ma*3; y=ma*3-c*2; w=1; c++; } printf("%lld %lld %lld\n",x,y,w); } }

컴파일 시 표준 에러 (stderr) 메시지

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  scanf("%lld%lld",&n,&d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
#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...