Submission #120884

#	Time	Username	Problem	Language	Result	Execution time	Memory
120884		faustaadp	Seats (IOI18_seats)	C++17	0 / 100	4094 ms	72420 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int x[2][1010101],n,i,j,mx,Mx,my,My,has=0;
int ST[2][2][4040404];
int mi[2][1010101];
int ma[2][1010101];
void upd(int aa,int bb,int cc,int dd,int ee)
{
	if(aa==bb)
	{
		ST[0][dd][ee]=x[dd][aa];
		ST[1][dd][ee]=x[dd][aa];
	}
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,dd,ee*2);
		else
			upd(ce+1,bb,cc,dd,ee*2+1);
		ST[0][dd][ee]=min(ST[0][dd][ee*2],ST[0][dd][ee*2+1]);
		ST[1][dd][ee]=max(ST[1][dd][ee*2],ST[1][dd][ee*2+1]);
	}
}
void cari(int aa,int bb,int cc,int dd,int ee)
{
	if(bb<cc||dd<aa)
		return ;
	else
	if(cc<=aa&&bb<=dd)
	{
		mx=min(mx,ST[0][0][ee]);
		Mx=max(Mx,ST[1][0][ee]);
		my=min(my,ST[0][1][ee]);
		My=max(My,ST[1][1][ee]);
	}
	else
	{
		int ce=(aa+bb)/2;
		cari(aa,ce,cc,dd,ee*2);
		cari(ce+1,bb,cc,dd,ee*2+1);
	}
}
ll cek(ll aa)
{
	return((ma[0][aa]-mi[0][aa]+1)*(ma[1][aa]-mi[1][aa]+1)==aa+1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
	n=H*W;
	for(i=0;i<H*W;i++)
	{
		x[0][i]=R[i];
		x[1][i]=C[i];
		if(i==0)
		{
			mi[0][i]=x[0][i];
			mi[1][i]=x[1][i];
			ma[0][i]=x[0][i];
			ma[1][i]=x[1][i];
		}
		else
		{
			mi[0][i]=min(mi[0][i-1],x[0][i]);
			mi[1][i]=min(mi[1][i-1],x[1][i]);
			ma[0][i]=max(ma[0][i-1],x[0][i]);
			ma[1][i]=max(ma[1][i-1],x[1][i]);
		}
		has+=cek(i);
		upd(0,n-1,i,0,1);
		upd(0,n-1,i,1,1);
	}
}
int swap_seats(int a, int b) 
{
	//return has;
	for(i=a;i<=b;i++)
		has-=cek(i);
	swap(x[1][a],x[1][b]);
	swap(x[0][a],x[0][b]);
	for(i=a;i<=n;i++)
	{
		if(i==0)
		{
			mi[0][i]=x[0][i];
			mi[1][i]=x[1][i];
			ma[0][i]=x[0][i];
			ma[1][i]=x[1][i];
		}
		else
		{	
			mi[0][i]=min(mi[0][i-1],x[0][i]);
			mi[1][i]=min(mi[1][i-1],x[1][i]);
			ma[0][i]=max(ma[0][i-1],x[0][i]);
			ma[1][i]=max(ma[1][i-1],x[1][i]);
		}
		has+=cek(i);
	}
	return has;
	// upd(0,n-1,a,0,1);
	// upd(0,n-1,a,1,1);
	// upd(0,n-1,b,0,1);
	// upd(0,n-1,b,1,1);
	int hz=0;
	//cout<<"A";
	//return 0;
	int too=0;
	mx=x[0][0];
	Mx=x[0][0];
	my=x[1][0];
	My=x[1][0];
	for(i=0;i<n;i++)
	{
		too++;
		cari(0,n-1,0,i,1);
		// mx=min(mx,x[0][i]);
		// Mx=max(Mx,x[0][i]);
		// my=min(my,x[1][i]);
		// My=max(My,x[1][i]);
		int tem=(Mx-mx+1)*(My-my+1);
		if(tem==i+1)hz++;
	//	cout<<i<<" "<<tem<<"\n";
		i=max(i,tem-2);
	}
	//if(too>4020)n/=0;
  	return hz;
}

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