Submission #208663

#	Time	Username	Problem	Language	Result	Execution time	Memory
208663		Lawliet	Seats (IOI18_seats)	C++17	100 / 100	3941 ms	105152 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 1000010;

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void refresh(int node, int l, int r)
		{
			if( lazy[node] == 0 ) return;

			int lz = lazy[node];
			lazy[node] = 0;

			mn[node] += lz;

			if( l == r ) return;

			lazy[ getLeft(node) ] += lz;
			lazy[ getRight(node) ] += lz;
		}

		void merge(int node, int idLeft, int idRight)
		{
			qtd[node] = 0;

			if( mn[idLeft] <= mn[idRight] )
			{
				mn[node] = mn[idLeft];
				qtd[node] += qtd[idLeft];
			}

			if( mn[idLeft] >= mn[idRight] )
			{
				mn[node] = mn[idRight];
				qtd[node] += qtd[idRight];
			}
		}

		void build(int node, int l, int r)
		{
			mn[node] = lazy[node] = 0;

			if( l == r ) return void( qtd[node] = 1 );

			int m = ( l + r )/2;

			build( getLeft(node) , l , m );
			build( getRight(node) , m + 1 , r );

			merge( node , getLeft(node) , getRight(node) );
		}

		void update(int node, int l, int r, int i, int j, int v)
		{
			if( i > j ) return;

			refresh( node , l , r );

			if( j < l || r < i ) return;
			if( i <= l && r <= j )
			{
				lazy[node] += v;
				refresh( node , l , r );

				return;
			}

			int m = ( l + r )/2;

			update( getLeft(node) , l , m , i , j , v );
			update( getRight(node) , m + 1 , r , i , j , v );

			merge( node , getLeft(node) , getRight(node) );
		}

		int qtdMin()
		{
			refresh( 1 , 1 , last );

			if( mn[1] != 4 ) return 0;
			return qtd[1];
		}

		void init(int R)
		{
			last = R;
			build( 1 , 1 , last );
		}

	private:

		int last;

		int mn[4*MAXN];
		int qtd[4*MAXN];
		int lazy[4*MAXN];
};

int n, m;

pii loc[MAXN];

vector< vector<int> > v;

SegmentTree SEG;

void updateSquare(int x, int y, int val)
{
	vector< int > aux;

	aux.push_back( v[x][y] );
	aux.push_back( v[x + 1][y] );
	aux.push_back( v[x][y + 1] );
	aux.push_back( v[x + 1][y + 1] );

	sort( aux.begin() , aux.end() );

	SEG.update( 1 , 1 , n*m , aux[0] , aux[1] - 1 , val );
	SEG.update( 1 , 1 , n*m , aux[2] , aux[3] - 1 , val );	
}

void changeSquare(int x, int y, int val)
{
	updateSquare( x - 1 , y - 1 , val );
	updateSquare( x , y - 1 , val );
	updateSquare( x - 1 , y , val );
	updateSquare( x , y , val );
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) 
{
	n = H; m = W;

	SEG.init( H*W );

	v.resize( n + 2 );

	for(int i = 0 ; i <= n + 1 ; i++)
		v[i].resize( m + 2 , n*m + 1 );

	for(int i = 0 ; i < n*m ; i++)
	{
		R[i]++; C[i]++;

		v[ R[i] ][ C[i] ] = i + 1;
		loc[i + 1] = { R[i] , C[i] };
	}

	for(int i = 0 ; i <= n ; i++)
		for(int j = 0 ; j <= m ; j++)
			updateSquare( i , j , 1 );
}

int swap_seats(int a, int b) 
{
	a++; b++;
	int xA = loc[a].first;
	int yA = loc[a].second;
	int xB = loc[b].first;
	int yB = loc[b].second;

	changeSquare( xA , yA , -1 );
	changeSquare( xB , yB , -1 );

	swap( loc[a] , loc[b] );
	swap( v[xA][yA] , v[xB][yB] );

	changeSquare( xA , yA , 1 );
	changeSquare( xB , yB , 1 );

	return SEG.qtdMin();
}

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