Submission #118341

#	Time	Username	Problem	Language	Result	Execution time	Memory
118341		joseacaz	Seats (IOI18_seats)	C++17	31 / 100	4029 ms	65180 KiB

seats

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

using namespace std;

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

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;
	swap ( R, _r );
	swap ( C, _c );

	N = H * W;
	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 ();
}

int swap_seats ( int a, int b )
{
	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] );

	maximR = -1, minimR = INF;
	maximC = -1, minimC = INF;
	ans = 0, last = 0;
	for ( int i = 0; i < H * W; )
	{
		maximR = max ( maximR, qryrow ( last, i, 0 ) );
		minimR = min ( minimR, qryrow ( last, i, 1 ) );
		maximC = max ( maximC, qrycol ( last, i, 0 ) );
		minimC = min ( minimC, qrycol ( last, i, 1 ) );
		//cout << i << ", {" << minimR << ", " << maximR << "}, {" << minimC << ", " << maximC << "}\n";
		last = i;

		if ( (maximR - minimR + 1) * (maximC - minimC + 1) == i + 1 )
			ans++;

		if ( (maximR - minimR + 1) * (maximC - minimC + 1) > i + 1 )
			i = (maximR - minimR + 1) * (maximC - minimC + 1) - 1;
		else
			i++;
	}

	return ans;
}

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