Submission #1066783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066783		Muhammad_Aneeq	자리 배치 (IOI18_seats)	C++17	0 / 100	4058 ms	32448 KiB

seats

#pragma GCC optimze("O2")
#include <vector>
using namespace std;
int h,w;
int const N=1e6+10;
struct node
{
	int mx=0,my=0,mix=1e9,miy=1e9;	
};
pair<int,int>seat[N]={};
node St[4*N]={};
int fen[N]={};
void add(int x,int val)
{
	while (x<N)
	{
		fen[x]+=val;
		x=(x|(x+1));
	}
}
int get(int r)
{
	int s=0;
	while (r>=0)
	{
		s+=fen[r];
		r=(r&(r+1))-1;
	}
	return s;
}
int sum(int l,int r)
{
	return get(r)-get(l-1);
}
node comb(node a,node b)
{
	node c;
	c.mx=max(a.mx,b.mx);
	c.mix=min(a.mix,b.mix);
	c.my=max(a.my,b.my);
	c.miy=min(a.miy,b.miy);
	return c;
}
void build(int i,int st,int en)
{
	if (st==en)
	{
		St[i].mx=St[i].mix=seat[st].first;
		St[i].my=St[i].miy=seat[st].second;
		return;
	}
	int mid=(st+en)/2;
	St[i]=comb(St[i*2],St[i*2+1]);
}
void update(int i,int r,int st,int en)
{
	if (st==en)
	{
		St[i].mx=St[i].mix=seat[st].first;
		St[i].my=St[i].miy=seat[st].second;
		return;
	}
	int mid=(st+en)/2;
	if (r<=mid)
		update(i*2,r,st,mid);
	else
		update(i*2+1,r,mid+1,en);
	St[i]=comb(St[i*2],St[i*2+1]);
}
node get(int i,int st,int en,int l,int r)
{
	if (l>r)
	{
		node a;
		return a;
	}
	if (st>=l&&en<=r)
		return St[i];
	if (st>r||en<l)
	{
		node a;
		return a;
	}
	int mid=(st+en)/2;
	return comb(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	h=H,w=W;
	for (int i=0;i<H*W;i++)
		seat[i]={R[i],C[i]};
	build(1,0,h*w-1);
	int x=0,mx=1e9;
	int y=0,my=1e9;
	for (int k=0;k<h*w;k++)
	{
		x=max(x,seat[k].first);
		mx=min(mx,seat[k].first);
		y=max(y,seat[k].second);
		my=min(my,seat[k].second);
		if ((x-mx+1)*(y-my+1)==k+1)
		{
			if (sum(k,k)==0)
				add(k,1);
		}
		else if (sum(k,k))
			add(k,-1);
	}
}
int swap_seats(int a, int b)
{
	swap(seat[a],seat[b]);
	update(1,a,0,h*w-1);
	update(1,b,0,h*w-1);
	int x=0,mx=1e9;
	int y=0,my=1e9;
	node z=get(1,0,h*w,0,min(a,b)-1);
	x=z.mx,y=z.my;
	mx=z.mix,my=z.miy;
	for (int k=min(a,b);k<=max(a,b);k++)
	{
		x=max(x,seat[k].first);
		mx=min(mx,seat[k].first);
		y=max(y,seat[k].second);
		my=min(my,seat[k].second);
		if ((x-mx+1)*(y-my+1)==k+1)
		{
			if (sum(k,k)==0)
				add(k,1);
		}
		else if (sum(k,k))
			add(k,-1);
	}
	return sum(0,h*w-1);
}

Compilation message (stderr)

seats.cpp:1: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
    1 | #pragma GCC optimze("O2")
      | 
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:52:6: warning: unused variable 'mid' [-Wunused-variable]
   52 |  int mid=(st+en)/2;
      |      ^~~

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