Submission #118360

#	Time	Username	Problem	Language	Result	Execution time	Memory
118360		joseacaz	Seats (IOI18_seats)	C++17	37 / 100	4017 ms	48604 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)

using namespace std;

int N, H, W, maximR[MAXN], minimR[MAXN], maximC[MAXN], minimC[MAXN], ans;
int STrow[2*MAXN + 5][2], STcol[2*MAXN + 5][2], last;
vector <int> R, C;
int maxR, minR, maxC, minC;

void build ( )
{
	for ( int i = N - 1; i; i-- )
	{
		STrow[i][0] = max ( STrow[2*i][0], STrow[2*i + 1][0] );
		STrow[i][1] = min ( STrow[2*i][1], STrow[2*i + 1][1] );
 
		STcol[i][0] = max ( STcol[2*i][0], STcol[2*i + 1][0] );
		STcol[i][1] = min ( STcol[2*i][1], STcol[2*i + 1][1] );
	}
}
 
int qryrow ( int l, int r, bool f )
{
	l += N, r += N;
	r++;
	int leftRes = (!f ? -1 : INF);
	int rightRes = (!f ? -1 : INF);
 
	for ( ; l < r; l /= 2, r /= 2 )
	{
		if ( f == 0 )
		{
			if ( l & 1 )
				leftRes = max ( leftRes, STrow[l++][f] );
			if ( r & 1 )
				rightRes = max ( rightRes, STrow[--r][f] );
		}
		else
		{
			if ( l & 1 )
				leftRes = min ( leftRes, STrow[l++][f] );
			if ( r & 1 )
				rightRes = min ( rightRes, STrow[--r][f] );	
		}
	}
 
	if ( !f )
		return max ( leftRes, rightRes );
	else
		return min ( leftRes, rightRes );
}
 
int qrycol ( int l, int r, bool f )
{
	l += N, r += N;
	r++;
	int leftRes = (!f ? -1 : INF);
	int rightRes = (!f ? -1 : INF);
 
	for ( ; l < r; l /= 2, r /= 2 )
	{
		if ( f == 0 )
		{
			if ( l & 1 )
				leftRes = max ( leftRes, STcol[l++][f] );
			if ( r & 1 )
				rightRes = max ( rightRes, STcol[--r][f] );
		}
		else
		{
			if ( l & 1 )
				leftRes = min ( leftRes, STcol[l++][f] );
			if ( r & 1 )
				rightRes = min ( rightRes, STcol[--r][f] );	
		}
	}
 
	if ( !f )
		return max ( leftRes, rightRes );
	else
		return min ( leftRes, rightRes );
}
 
void updrow ( int pos, int x )
{
	STrow[N + pos][0] = x;
	STrow[N + pos][1] = x;
 
	for ( int i = (pos + N) / 2; i; i /= 2 )
	{
		STrow[i][0] = max ( STrow[2*i][0], STrow[2*i + 1][0] );
		STrow[i][1] = min ( STrow[2*i][1], STrow[2*i + 1][1] );
	}
}
 
void updcol ( int pos, int x )
{
	STcol[N + pos][0] = x;
	STcol[N + pos][1] = x;
 
	for ( int i = (pos + N) / 2; i; i /= 2 )
	{
		STcol[i][0] = max ( STcol[2*i][0], STcol[2*i + 1][0] );
		STcol[i][1] = min ( STcol[2*i][1], STcol[2*i + 1][1] );
	}
}

void give_initial_chart ( int _h, int _w, vector <int> _r, vector <int> _c )
{
	H = _h;
	W = _w;
	N = H * W;
	swap ( R, _r );
	swap ( C, _c );

	if ( H <= 1000 && W <= 1000 )
	{
		for ( int i = N; i < 2 * N; i++ )
		{
			STrow[i][0] = R[i - N];
			STrow[i][1] = R[i - N];
	 
			STcol[i][0] = C[i - N];
			STcol[i][1] = C[i - N];
		}
		build ();
	}
	else
	{
		maximR[0] = R[0];
		minimR[0] = R[0];
		maximC[0] = C[0];
		minimC[0] = C[0];
		ans++;

		for ( int i = 1; i < H * W; i++ )
		{
			maximR[i] = max ( maximR[i - 1], R[i] );
			minimR[i] = min ( minimR[i - 1], R[i] );
			maximC[i] = max ( maximC[i - 1], C[i] );
			minimC[i] = min ( minimC[i - 1], C[i] );
	 
			if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
				ans++;
		}
	}
}

int swap_seats ( int a, int b )
{
	if ( H <= 1000 && W <= 1000 )
	{
		swap ( R[a], R[b] );
		updrow ( a, R[a] );
		updrow ( b, R[b] );
	 
		swap ( C[a], C[b] );
		updcol ( a, C[a] );
		updcol ( b, C[b] );
	 
		maxR = -1, minR = INF;
		maxC = -1, minC = INF;
		ans = 0, last = 0;
		for ( int i = 0; i < H * W; )
		{
			maxR = max ( maxR, qryrow ( last, i, 0 ) );
			minR = min ( minR, qryrow ( last, i, 1 ) );
			maxC = max ( maxC, qrycol ( last, i, 0 ) );
			minC = min ( minC, qrycol ( last, i, 1 ) );
			last = i;
	 
			if ( (maxR - minR + 1) * (maxC - minC + 1) == i + 1 )
				ans++;
	 
			if ( (maxR - minR + 1) * (maxC - minC + 1) > i + 1 )
				i = (maxR - minR + 1) * (maxC - minC + 1) - 1;
			else
				i++;
		}
	}
	else
	{
		swap ( R[a], R[b] );
		swap ( C[a], C[b] );
		
		if ( a > b )
			swap ( a, b );
		for ( int i = a; i <= b; i++ )
		{
			if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
				ans--;
				
			if ( i == 0 )
			{
				maximR[0] = R[0];
				minimR[0] = R[0];
				maximC[0] = C[0];
				minimC[0] = C[0];
			}
			else
			{
				maximR[i] = max ( maximR[i - 1], R[i] );
				minimR[i] = min ( minimR[i - 1], R[i] );
				maximC[i] = max ( maximC[i - 1], C[i] );
				minimC[i] = min ( minimC[i - 1], C[i] );
			}
	 
			if ( (maximR[i] - minimR[i] + 1) * (maximC[i] - minimC[i] + 1) == i + 1 )
				ans++;
		}
	}

	return ans;
}

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