Submission #1066862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066862		Muhammad_Aneeq	Seats (IOI18_seats)	C++17	20 / 100	3591 ms	57692 KiB

seats

#pragma GCC optimze("O2")
#include <vector>
#include <iostream>
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[2097152]={};
bool fen[N]={};
node extra;
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;
}
int ans=0;
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;
	build(i*2,st,mid);
	build(i*2+1,mid+1,en);
	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)
		return extra;
	if (st>=l&&en<=r)
		return St[i];
	if (st>r||en<l)
		return extra;
	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)
		{
			fen[k]=1;
			ans++;
		}
	}
}
int swap_seats(int a, int b)
{
	swap(seat[a],seat[b]);
	update(1,min(a,b),0,h*w-1);
	update(1,max(a,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 (fen[k]==0)
				ans++;
			fen[k]=1;
		}
		else if (fen[k])
		{
			fen[k]=0;
			ans--;
		}
	}
	return ans;
}

Compilation message (stderr)

seats.cpp:1: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
    1 | #pragma GCC optimze("O2")
      |

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