Submission #118359

#	Time	Username	Problem	Language	Result	Execution time	Memory
118359		joseacaz	Seats (IOI18_seats)	C++17	17 / 100	4082 ms	41336 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;
vector <int> R, C;

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

	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 )
{
	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: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30