제출 #421159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421159		Pyqe	Izvanzemaljci (COI21_izvanzemaljci)	C++14	68 / 100	3063 ms	25416 KiB

izvanzemaljci

#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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 12 / 12
• Subtask 4: 30 / 30
• Subtask 5: 0 / 32