Submission #118372

#	Time	Username	Problem	Language	Result	Execution time	Memory
118372		joseacaz	Seats (IOI18_seats)	C++17	100 / 100	3818 ms	95512 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;

struct Node
{
	int minim, freq;

	Node operator + ( const Node& _x ) const
	{
		Node aux;
		if ( minim < _x.minim )
			aux.minim = minim, aux.freq = freq;
		else if ( minim > _x.minim )
			aux.minim = _x.minim, aux.freq = _x.freq;
		else
			aux.minim = minim, aux.freq = freq + _x.freq;

		return aux;
	}

	void out ()
	{
		cout << minim << " " << freq << "\n";
	}
};

int N, H, W;
vector <int> R, C, A;
vector <vector <int>> seats;
Node ST[4 * MAXN], DEFAULT;
int lazy[4 * MAXN];

void propagate ( int node, int l, int r )
{
	ST[node].minim += lazy[node];
	if ( l != r )
	{
		VARS;
		lazy[lchild] += lazy[node];
		lazy[rchild] += lazy[node];
	}
	lazy[node] = 0;
}

void build ( int node = 0, int l = 0, int r = N - 1 )
{
	if ( l == r )
	{
		ST[node].minim = 0;
		ST[node].freq = 1;
		return;
	}

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

	ST[node] = ST[lchild] + ST[rchild];
}

void upd ( int L, int R, int x, int node = 0, int l = 0, int r = N - 1 )
{
	propagate ( node, l, r );
	if ( r < L or R < l )
		return;
	if ( L <= l && r <= R )
	{
		lazy[node] = x;
		propagate ( node, l, r );
		return;
	}

	VARS;
	upd ( L, R, x, lchild, l, mid );
	upd ( L, R, x, rchild, mid + 1, r );

	ST[node] = ST[lchild] + ST[rchild];
}

Node qry ( int L, int R, int node = 0, int l = 0, int r = N - 1 )
{
	propagate ( node, l, r );
	if ( r < L or R < l )
		return DEFAULT;
	if ( L <= l && r <= R )
		return ST[node];
	
	VARS;
	return qry ( L, R, lchild, l, mid ) + qry ( L, R, rchild, mid + 1, r );
}

void give_initial_chart ( int _h, int _w, vector <int> _r, vector <int> _c )
{
	DEFAULT.minim = INF;
	DEFAULT.freq = 0;

	H = _h;
	W = _w;
	N = H * W;
	swap ( R, _r );
	swap ( C, _c );
	seats.resize ( H + 5 );
	for ( int i = 0; i < H + 5; i++ )
		seats[i].resize ( W + 5 );
	
	for ( int i = 0; i <= W + 1; i++ )
		seats[0][i] = N, seats[H + 1][i] = N;
	for ( int i = 0; i <= H + 1; i++ )
		seats[i][0] = N, seats[i][W + 1] = N;
	for ( int i = 0; i < N; i++ )
		seats[R[i] + 1][C[i] + 1] = i;
	
	build ( );
	for ( int i = 0; i <= H; i++ )
	{
		for ( int j = 0; j <= W; j++ )
		{
			A.clear();
			A.push_back ( seats[i][j] );
			A.push_back ( seats[i][j + 1] );
			A.push_back ( seats[i + 1][j] );
			A.push_back ( seats[i + 1][j + 1] );
			sort ( A.begin(), A.end() );
			
			upd ( A[0], A[1] - 1, 1 );
			upd ( A[2], A[3] - 1, 1 );
		}
	}

}

int swap_seats ( int a, int b )
{
	for ( int i = R[a]; i <= R[a] + 1; i++ )
	{
		for ( int j = C[a]; j <= C[a] + 1; j++ )
		{
			A.clear();
			A.push_back ( seats[i][j] );
			A.push_back ( seats[i][j + 1] );
			A.push_back ( seats[i + 1][j] );
			A.push_back ( seats[i + 1][j + 1] );
			sort ( A.begin(), A.end() );
			
			upd ( A[0], A[1] - 1, -1 );
			upd ( A[2], A[3] - 1, -1 );
		}
	}

	for ( int i = R[b]; i <= R[b] + 1; i++ )
	{
		for ( int j = C[b]; j <= C[b] + 1; j++ )
		{
			A.clear();
			A.push_back ( seats[i][j] );
			A.push_back ( seats[i][j + 1] );
			A.push_back ( seats[i + 1][j] );
			A.push_back ( seats[i + 1][j + 1] );
			sort ( A.begin(), A.end() );
			
			upd ( A[0], A[1] - 1, -1 );
			upd ( A[2], A[3] - 1, -1 );
		}
	}

	swap ( seats[R[a] + 1][C[a] + 1], seats[R[b] + 1][C[b] + 1] );
	swap ( R[a], R[b] );
	swap ( C[a], C[b] );

	for ( int i = R[a]; i <= R[a] + 1; i++ )
	{
		for ( int j = C[a]; j <= C[a] + 1; j++ )
		{
			A.clear();
			A.push_back ( seats[i][j] );
			A.push_back ( seats[i][j + 1] );
			A.push_back ( seats[i + 1][j] );
			A.push_back ( seats[i + 1][j + 1] );
			sort ( A.begin(), A.end() );
			
			upd ( A[0], A[1] - 1, 1 );
			upd ( A[2], A[3] - 1, 1 );
		}
	}

	for ( int i = R[b]; i <= R[b] + 1; i++ )
	{
		for ( int j = C[b]; j <= C[b] + 1; j++ )
		{
			A.clear();
			A.push_back ( seats[i][j] );
			A.push_back ( seats[i][j + 1] );
			A.push_back ( seats[i + 1][j] );
			A.push_back ( seats[i + 1][j + 1] );
			sort ( A.begin(), A.end() );
			
			upd ( A[0], A[1] - 1, 1 );
			upd ( A[2], A[3] - 1, 1 );
		}
	}

	propagate ( 0, 0, N - 1 );
	if ( ST[0].minim == 4 )
		return ST[0].freq;
	return 0;
}

Compilation message (stderr)

seats.cpp: In function 'void propagate(int, int, int)':
seats.cpp:5:18: warning: unused variable 'mid' [-Wunused-variable]
 #define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2
                  ^
seats.cpp:43:3: note: in expansion of macro 'VARS'
   VARS;
   ^~~~

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