제출 #986399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986399		Pyqe	자리 배치 (IOI18_seats)	C++17	100 / 100	1617 ms	177896 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,m,a[1000069],ya[1000069],xa[1000069],vy[4]={-1,0,1,0},vx[4]={0,1,0,-1},inf=1e9;
pair<int,int> ps[1000069];
bool alr=0;

struct segtree
{
	int l,r,c;
	pair<int,int> mn,lz={0,0};
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		if(l==r)
		{
			mn=ps[l];
			mn.sc+=l+1;
			c=1;
		}
		else
		{
			int 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);
			}
			mn=min(p[0]->mn,p[1]->mn);
			c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
		}
	}
	inline void blc()
	{
		if(lz!=mp(0,0))
		{
			int ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->mn.fr+=lz.fr;
				p[ii]->mn.sc+=lz.sc;
				p[ii]->lz.fr+=lz.fr;
				p[ii]->lz.sc+=lz.sc;
			}
			lz={0,0};
		}
	}
	void ud(int ky,int lh,int rh,int w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			if(!ky)
			{
				mn.fr+=w;
				lz.fr+=w;
			}
			else
			{
				mn.sc+=w;
				lz.sc+=w;
			}
		}
		else
		{
			int ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(ky,lh,rh,w);
			}
			mn=min(p[0]->mn,p[1]->mn);
			c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
		}
	}
}
sg;

void acv(int y,int x,int u)
{
	int i,j,im,p=y*m+x,yy,xx,pp,mn[2]={inf,inf};
	
	for(im=0;im<4;im++)
	{
		yy=y+vy[im];
		xx=x+vx[im];
		if(yy>=0&&xx>=0&&yy<n&&xx<m)
		{
			pp=yy*m+xx;
			for(i=0;i<2;i++)
			{
				if(a[pp]<mn[i])
				{
					for(j=1;j>i;j--)
					{
						mn[j]=mn[j-1];
					}
					mn[i]=a[pp];
					break;
				}
			}
		}
	}
	if(alr)
	{
		sg.ud(0,mn[1],a[p]-1,u);
	}
	else if(mn[1]<=a[p])
	{
		ps[mn[1]].fr+=u;
		ps[a[p]].fr-=u;
	}
}

void give_initial_chart(int on,int om,vector<int> yaa,vector<int> xaa)
{
	int i,j,p;
	
	n=on;
	m=om;
	for(i=0;i<n*m;i++)
	{
		ya[i]=yaa[i];
		xa[i]=xaa[i];
		a[ya[i]*m+xa[i]]=i;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			p=i*m+j;
			acv(i,j,1);
			if(i)
			{
				ps[max(a[p],a[p-m])].sc--;
			}
			if(j)
			{
				ps[max(a[p],a[p-1])].sc--;
			}
			if(i&&j)
			{
				ps[max(max(a[p],a[p-1]),max(a[p-m],a[p-m-1]))].sc++;
			}
		}
	}
	for(i=1;i<n*m;i++)
	{
		ps[i].fr+=ps[i-1].fr;
		ps[i].sc+=ps[i-1].sc;
	}
	sg.bd(0,n*m-1);
	alr=1;
}

int swap_seats(int w,int w2)
{
	int i,ii,iii,im,u,y,x,p,yy,xx,pp;
	
	for(ii=0;ii<2;ii++)
	{
		y=ya[w];
		x=xa[w];
		p=y*m+x;
		for(iii=0;iii<2;iii++)
		{
			u=iii*2-1;
			acv(y,x,u);
			for(im=0;im<4;im++)
			{
				yy=y+vy[im];
				xx=x+vx[im];
				if(yy>=0&&xx>=0&&yy<n&&xx<m)
				{
					pp=yy*m+xx;
					acv(yy,xx,u);
					sg.ud(1,max(a[p],a[pp]),n*m-1,-u);
				}
				yy=y+im/2;
				xx=x+im%2;
				if(yy>0&&xx>0&&yy<n&&xx<m)
				{
					pp=yy*m+xx;
					sg.ud(1,max(max(a[pp],a[pp-1]),max(a[pp-m],a[pp-m-1])),n*m-1,u);
				}
			}
			a[p]=w2;
		}
		swap(w,w2);
	}
	swap(ya[w],ya[w2]);
	swap(xa[w],xa[w2]);
	return sg.c;
}

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

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:170:6: warning: unused variable 'i' [-Wunused-variable]
  170 |  int i,ii,iii,im,u,y,x,p,yy,xx,pp;
      |      ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30