Submission #114182

#	Time	Username	Problem	Language	Result	Execution time	Memory
114182		antimirage	Seats (IOI18_seats)	C++14	31 / 100	4093 ms	62044 KiB

seats

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

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e6 + 5;

int ans, t[4][N * 4], n, ar[4];

vector <int> r, c;

void build (int v = 1, int tl = 0, int tr = n - 1)
{
	if (tl == tr){
		t[0][v] = r[tl], t[1][v] = r[tl];
		t[2][v] = c[tl], t[3][v] = c[tl];
	}
	else{
		
		int tm = (tl + tr) >> 1;
		build( v + v, tl, tm );
		build( v + v + 1, tm + 1, tr );
	
		t[0][v] = min( t[0][v + v], t[0][v + v + 1] );
		t[1][v] = max( t[1][v + v], t[1][v + v + 1] );
		t[2][v] = min( t[2][v + v], t[2][v + v + 1] );
		t[3][v] = max( t[3][v + v], t[3][v + v + 1] );
	}
}
void update (int pos, int v = 1, int tl = 0, int tr = n - 1)
{
	if (tl == tr){
		t[0][v] = r[tl], t[1][v] = r[tl];
		t[2][v] = c[tl], t[3][v] = c[tl];
	}
	else{
		int tm = (tl + tr) >> 1;
		
		if (pos <= tm)
			update( pos, v + v, tl, tm );
		else
			update( pos, v + v + 1, tm + 1, tr );
			
		t[0][v] = min( t[0][v + v], t[0][v + v + 1] );
		t[1][v] = max( t[1][v + v], t[1][v + v + 1] );
		t[2][v] = min( t[2][v + v], t[2][v + v + 1] );
		t[3][v] = max( t[3][v + v], t[3][v + v + 1] );
	}
}

void calc (int v = 1, int tl = 0, int tr = n - 1)
{
	if (t[0][v] >= ar[0] && t[1][v] <= ar[1] && t[2][v] >= ar[2] && t[3][v] <= ar[3]) { 
	
		if ( (ar[1] - ar[0] + 1) * (ar[3] - ar[2] + 1) == tr + 1 ){
			ans++;
		}
		return;
	}
		
	if (tl == tr){
		ar[0] = min(ar[0], t[0][v]);
		ar[1] = max(ar[1], t[1][v]);
		ar[2] = min(ar[2], t[2][v]);
		ar[3] = max(ar[3], t[3][v]);
		
		if ( (ar[1] - ar[0] + 1) * (ar[3] - ar[2] + 1) == tl + 1 ){
			ans++;
		}
	}
	else{
		int tm = (tl + tr) >> 1;
		
		calc(v + v, tl, tm);
		calc(v + v + 1, tm + 1, tr);
	}
}

void give_initial_chart(int N, int M, vector<int> R, vector<int> C) {

	r = R;
	c = C;
	
	n = N * M;
	
	build();
}

int swap_seats(int a, int b) {
	
	swap( r[a], r[b] );
	swap( c[a], c[b] );
	
	update( a );
	update( b );
	
	
	ans = 0;
	
	ar[0] = r[0];
	ar[1] = r[0];
	
	ar[2] = c[0];
	ar[3] = c[0];
	
	calc( );
	
	return ans;
}
/**
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
**/

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