Submission #208654

#	Time	Username	Problem	Language	Result	Execution time	Memory
208654		Lawliet	자리 배치 (IOI18_seats)	C++17	37 / 100	4081 ms	121292 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)
		{
			int lz[] = { lazy[node][0] , lazy[node][1] };
			lazy[node][0] = lazy[node][1] = 0;

			for(int i = 0 ; i < 2 ; i++)
				mn[node][i] += lz[i];

			if( l == r ) return;

			for(int i = 0 ; i < 2 ; i++)
			{
				lazy[ getLeft(node) ][i] += lz[i];
				lazy[ getRight(node) ][i] += lz[i];
			}
		}

		void merge(int node, int idLeft, int idRight)
		{
			qtd[node] = 0;
			pii L = { mn[idLeft][0] , mn[idLeft][1] };
			pii R = { mn[idRight][0] , mn[idRight][1] };

			if( L <= R )
			{
				mn[node][0] = L.first;
				mn[node][1] = L.second;

				qtd[node] += qtd[idLeft];
			}

			if( R <= L )
			{
				mn[node][0] = R.first;
				mn[node][1] = R.second;

				qtd[node] += qtd[idRight];
			}
		}

		void build(int node, int l, int r)
		{
			mn[node][0] = mn[node][1] = 0;
			lazy[node][0] = lazy[node][1] = 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 p, int v)
		{
			if( i > j ) return;

			refresh( node , l , r );

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

				return;
			}

			int m = ( l + r )/2;

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

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

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

			pii min = { 4 , 0 };
			pii root = { mn[1][0] , mn[1][1] };

			if( root != min ) return 0;
			return qtd[1];
		}

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

	private:

		int last;

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

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

	for(int i = 0 ; i < 4 ; i++)
		for(int j = i - 1 ; j >= 0 ; j--)
			if( aux[j] < aux[j - 1] ) swap( aux[j] , aux[j - 1] );

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

	SEG.update( 1 , 1 , n*m , aux[0] , aux[1] - 1 , 0 , val );
	SEG.update( 1 , 1 , n*m , aux[2] , aux[3] - 1 , 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: 0 / 33
• Subtask 6: 0 / 30