Submission #118321

#	Time	Username	Problem	Language	Result	Execution time	Memory
118321		joseacaz	Seats (IOI18_seats)	C++17	5 / 100	4101 ms	57784 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
#define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2

using namespace std;

int H, W, STrow[4 * MAXN][2], STcol[4 * MAXN][2];
vector <int> R, C;

void buildrow ( int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( l == r )
	{
		STrow[node][0] = R[l];
		STrow[node][1] = R[l];
		return;
	}

	VARS;
	buildrow ( lchild, l, mid );
	buildrow ( rchild, mid + 1, r );

	STrow[node][0] = max ( STrow[lchild][0], STrow[rchild][0] );
	STrow[node][1] = min ( STrow[lchild][1], STrow[rchild][1] );
}

void buildcol ( int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( l == r )
	{
		STcol[node][0] = C[l];
		STcol[node][1] = C[l];
		return;
	}

	VARS;
	buildcol ( lchild, l, mid );
	buildcol ( rchild, mid + 1, r );

	STcol[node][0] = max ( STcol[lchild][0], STcol[rchild][0] );
	STcol[node][1] = min ( STcol[lchild][1], STcol[rchild][1] );
}

int qryrow ( int L, int R, bool f, int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( r < L or R < l )
		return (!f ? -1 : INF);
	if ( L <= l && r <= R )
		return STrow[node][f];
	
	VARS;
	if ( !f )
		return max ( qryrow ( L, R, f, lchild, l, mid ), qryrow ( L, R, f, rchild, mid + 1, r ) );
	else
		return min ( qryrow ( L, R, f, lchild, l, mid ), qryrow ( L, R, f, rchild, mid + 1, r ) );
}

int qrycol ( int L, int R, bool f, int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( r < L or R < l )
		return (!f ? -1 : INF);
	if ( L <= l && r <= R )
		return STcol[node][f];
	
	VARS;
	if ( !f )
		return max ( qrycol ( L, R, f, lchild, l, mid ), qrycol ( L, R, f, rchild, mid + 1, r ) );
	else
		return min ( qrycol ( L, R, f, lchild, l, mid ), qrycol ( L, R, f, rchild, mid + 1, r ) );
}

void updrow ( int pos, int x, int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( r < pos or pos < l )
		return;
	if ( l == r )
	{
		STrow[node][0] = x;
		STrow[node][1] = x;
		return;
	}

	VARS;
	updrow ( pos, x, lchild, l, mid );
	updrow ( pos, x, rchild, mid + 1, r );

	STrow[node][0] = max ( STrow[lchild][0], STrow[rchild][0] );
	STrow[node][1] = min ( STrow[lchild][1], STrow[rchild][1] );
}

void updcol ( int pos, int x, int node = 0, int l = 0, int r = H*W - 1 )
{
	if ( r < pos or pos < l )
		return;
	if ( l == r )
	{
		STcol[node][0] = x;
		STcol[node][1] = x;
		return;
	}

	VARS;
	updcol ( pos, x, lchild, l, mid );
	updcol ( pos, x, rchild, mid + 1, r );

	STcol[node][0] = max ( STcol[lchild][0], STcol[rchild][0] );
	STcol[node][1] = min ( STcol[lchild][1], STcol[rchild][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 );

	buildrow ();
	buildcol ();
}

int swap_seats ( int a, int b )
{
	if ( !(H <= 1000 && W <= 1000) )
		return 0;

	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] );

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

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

	return ans;
}

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