Submission #75629

#	Time	Username	Problem	Language	Result	Execution time	Memory
75629		joseacaz	Seats (IOI18_seats)	C++17	0 / 100	4029 ms	43544 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define vi vector < int >

using namespace std;

int N, M, tot, aux;
vector < int > R, C, LR, RR, UC, LC, ans;

void give_initial_chart ( int _h, int _w, vi _r, vi _c )
{
	N = _h;
	M = _w;
	R = _r;
	C = _c;
	LR.resize ( N * M );
	RR.resize ( N * M );
	UC.resize ( N * M );
	LC.resize ( N * M );
	ans.resize ( N * M );

	LR[0] = R[0];
	RR[0] = R[0];
	UC[0] = C[0];
	LC[0] = C[0];
	ans[0] = 1, tot = 1;
	for ( int i = 1; i < N * M; i++ )
	{
		LR[i] = min ( LR[i - 1], R[i] );
		RR[i] = max ( RR[i - 1], R[i] );
		UC[i] = min ( UC[i - 1], C[i] );
		LC[i] = max ( LC[i - 1], C[i] );
		if ( (RR[i] - LR[i] + 1) * (LC[i] - UC[i] + 1) == i + 1 )
			ans[i] = 1, tot++;
	}
}

int swap_seats ( int a, int b )
{
	aux = R[a];
	R[a] = R[b];
	R[b] = aux;

	aux = C[a];
	C[a] = C[b];
	C[b] = aux;

	tot -= ans[a], ans[a] = 0;
	if ( a > 0 )
	{
		LR[a] = min ( LR[a - 1], R[a] );
		RR[a] = max ( RR[a - 1], R[a] );
		UC[a] = min ( UC[a - 1], C[a] );
		LC[a] = max ( LC[a - 1], C[a] );
	}
	else
	{
		LR[0] = R[0];
		RR[0] = R[0];
		UC[0] = C[0];
		LC[0] = C[0];
	}
	ans[a] = 1, tot++;

	for ( int i = a + 1; i <= b; i++ )
	{
		tot -= ans[i], ans[i] = 0;
		LR[i] = min ( LR[i - 1], R[i] );
		RR[i] = max ( RR[i - 1], R[i] );
		UC[i] = min ( UC[i - 1], C[i] );
		LC[i] = max ( LC[i - 1], C[i] );
		if ( (RR[i] - LR[i] + 1) * (LC[i] - UC[i] + 1) == i + 1 )
			ans[i] = 1, tot++;
	}

	return tot;
}

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