Submission #294186

#	Time	Username	Problem	Language	Result	Execution time	Memory
294186		amoo_safar	Seats (IOI18_seats)	C++17	33 / 100	1666 ms	53044 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1e6 + 10;

vi R, C;
int H, W;
vector<vi> A;


pii seg[N << 2];
int lz[N << 2];
void Apply(int id, int x){
	lz[id] += x;
	seg[id].F += x;
}
void Shift(int id){
	Apply(id << 1, lz[id]);
	Apply(id << 1 | 1, lz[id]);
	lz[id] = 0;
}
void Build(int id = 1, int L = 0, int R = H * W){
	seg[id] = {0, R - L};
	lz[id] = 0;
	if(L + 1 == R) return ;
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
}
pii Merge(pii &AA, pii &BB){
	if(AA.F != BB.F) return min(AA, BB);
	return {AA.F, AA.S + BB.S};
}
int Val[N];
void Add(int id, int l, int r, int x, int L = 0, int R = H * W){
	//for(int i = l; i < r; i++) Val[i] += x;
	//return ;
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, x);
		return ;
	}
	Shift(id);
	int mid = (L + R) >> 1;
	Add(id << 1, l, r, x, L, mid);
	Add(id << 1 | 1, l, r, x, mid, R);
	seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
	return ;
}
int Calc(){
	return seg[1].F == 0 ? seg[1].S : 0;

	int res = 0;
	for(int i = 0; i < H*W; i++){
		assert(Val[i] >= 0);
		if(Val[i] == 0)
			res ++;
	}
	return res;
}
void AddEdge(int x1, int y1, int x2, int y2, int z){
	int val = max(A[x1][y1], A[x2][y2]);
	Add(1, val, H*W, -1 * z);
	//cerr << "!! " << val << " -> " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
}
void AddFace(int x, int y, int z){
	int val = max({A[x][y], A[x + 1][y], A[x][y + 1], A[x + 1][y + 1]});
	Add(1, val, H*W, +1 * z);
}

bool Valid(int i, int j){
	return (0 <= i) && (i < H) && (0 <= j) && (j < W);
}

bool ValidFace(int i, int j){
	return (0 <= i) && (i + 1 < H) && (0 <= j) && (j + 1 < W);
}

pii adjE[] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

pii adjF[] = {{-1, -1}, {-1, 0}, {0, -1}, {0, 0}};

void AddCell(int i, int j, int z){
	int nx, ny;
	for(auto [dx, dy] : adjE){
		nx = i + dx; ny = j + dy;
		if(!Valid(nx, ny)) continue;
		AddEdge(i, j, nx, ny, z);
	}
	for(auto [dx, dy] : adjF){
		nx = i + dx; ny = j + dy;
		if(!ValidFace(nx, ny)) continue;
		AddFace(nx, ny, z);
	}
}

void give_initial_chart(int _H, int _W, vi _R, vi _C){
	R = _R; C = _C;
	H = _H; W = _W;
	assert(H == 1);
	
	A.resize(H, vector<int> (W, 0));
	for(int i = 0; i < H * W; i++)
		A[R[i]][C[i]] = i;
	Build();
	for(int i = 0; i + 1 < H; i++)
		for(int j = 0; j < W; j++)
			AddEdge(i, j, i + 1, j, +1);
	for(int i = 0; i < H; i++)
		for(int j = 0; j + 1 < W; j++)
			AddEdge(i, j, i, j + 1, +1);
	for(int i = 0; i + 1 < H; i++)
		for(int j = 0; j + 1 < W; j++)
			AddFace(i, j, +1);
	/*
	for(int i = 0; i < H; i++)
		for(int j = 0; j < W; j++)
			AddCell(i, j, +1);
	*/

	for(int i = 0; i < H*W; i++)
		Add(1, i, i + 1, i);
	
	//for(int i = 0; i < H*W; i++) cerr << Val[i] << ' ';
	//cerr << "!\n";
	//cerr << Calc() << '\n';
	//cerr << seg[1].S << ' ' << "#########\n";
}

int swap_seats(int a, int b){
	//return 0;
	//for(int i = 0; i < H*W; i++)
	//	cerr << Val[i] << ' ';
	//cerr << "!\n";

	AddCell(R[a], C[a], -1);
	A[R[a]][C[a]] = b;
	AddCell(R[a], C[a], +1);
	
	AddCell(R[b], C[b], -1);
	A[R[b]][C[b]] = a;
	AddCell(R[b], C[b], +1);
	
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	//A[R[a]][C[a]] = a;
	//A[R[b]][C[b]] = b;
	/*
	for(int i = 0; i < H*W; i++)
		cerr << Val[i] << ' ';
	cerr << "?\n";
	*/
	return Calc();
}

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