Submission #96827

#	Time	Username	Problem	Language	Result	Execution time	Memory
96827		youngyojun	Seats (IOI18_seats)	C++11	100 / 100	2824 ms	124608 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 1000005;
int _int[MAXN*4], *_intp = _int;
int* newint(int n) { _intp += n; return _intp - n; }

struct SEG {
	int dp[MAXN*3][5], duc[MAXN*3], dbc[MAXN*3];
	bitset<MAXN*3> chk;
	int n;

	void init(int i, int s, int e) {
		dp[i][0] = e-s+1;
		if(s == e) return;
		int m = (s+e) >> 1;
		init(i<<1, s, m);
		init(i<<1|1, m+1, e);
	}
	void init(int _n) {
		n = _n;
		init(1, 0, n-1);
	}

	void mv(int d[], int w) {
		if(!w) return;
		for(int i = 5; w < i--;) d[i] = d[i-w];
		memset(d, 0, min(5, w)<<2);
	}
	void cal(int i, int s, int e) {
		memset(dp[i], 0, 20);
		if(dbc[i] || 4 < duc[i]) return;
		if(s == e) dp[i][0] = 1;
		else {
			for(int j = 5, t; j--;) {
				t = 0;
				if(!chk[i<<1]) t += dp[i<<1][j];
				if(!chk[i<<1|1]) t += dp[i<<1|1][j];
				dp[i][j] = t;
			}
		}
		mv(dp[i], duc[i]);
	}
	void precal(int i, int s, int e) {
		chk[i] = false;
		if(s == e) {
			cal(i, s, e);
			return;
		}
		int m = (s+e) >> 1, l = i<<1, r = l|1;
		if(chk[l] && !dbc[l] && duc[l] < 5) precal(l, s, m);
		if(chk[r] && !dbc[r] && duc[r] < 5) precal(r, m+1, e);
		cal(i, s, e);
	}
	void updb(int i, int s, int e, int p, int q, int x) {
		if(q < p || e < p || q < s) return;
		chk[i] = true;
		if(p <= s && e <= q) {
			dbc[i] += x;
			return;
		}
		int m = (s+e) >> 1;
		updb(i<<1, s, m, p, q, x);
		updb(i<<1|1, m+1, e, p, q, x);
	}
	void updu(int i, int s, int e, int p, int q, int x) {
		if(q < p || e < p || q < s) return;
		chk[i] = true;
		if(p <= s && e <= q) {
			duc[i] += x;
			return;
		}
		int m = (s+e) >> 1;
		updu(i<<1, s, m, p, q, x);
		updu(i<<1|1, m+1, e, p, q, x);
	}
	void updb(int s, int e, int x) { updb(1, 0, n-1, s, e, x); }
	void updu(int s, int e, int x) { updu(1, 0, n-1, s, e, x); }
	int get() {
		if(chk[1]) precal(1, 0, n-1);
		return dp[1][4];
	}
} seg;

int A[MAXN], B[MAXN], *C[MAXN];

int H, W, N;

vector<pii> PFV[2], NFV[2];
void f(int y, int x, bool flag = false) {
	int a[4] = { C[y][x], C[y][x+1], C[y+1][x], C[y+1][x+1] };
	sort(a, a+4);
	(flag ? NFV : PFV)[0].eb(a[0], a[1]-1);
	(flag ? NFV : PFV)[1].eb(a[2], a[3]-1);
}
void g(int i, bool flag = false) {
	int y = A[i], x = B[i];
	for(int dy = 2; dy--;) for(int dx = 2; dx--;)
		f(y-dy, x-dx, flag);
}
void run() {
	for(auto &v : PFV[0]) seg.updu(v.first, v.second, 1);
	for(auto &v : PFV[1]) seg.updb(v.first, v.second, 1);
	for(auto &v : NFV[0]) seg.updu(v.first, v.second, -1);
	for(auto &v : NFV[1]) seg.updb(v.first, v.second, -1);
	PFV[0].clear(); PFV[1].clear();
	NFV[0].clear(); NFV[1].clear();
}

void give_initial_chart(int H, int W, std::vector<int> RV, std::vector<int> CV) {
	::H = H; ::W = W; N = H*W;
	for(int i = H+2; i--;) {
		C[i] = newint(W+2);
		C[i][0] = C[i][W+1] = INF;
	}
	fill(C[0], C[0]+W+2, INF);
	fill(C[H+1], C[H+1]+W+2, INF);
	for(int i = N; i--;) {
		A[i] = RV[i] + 1;
		B[i] = CV[i] + 1;
		C[A[i]][B[i]] = i;
	}
	seg.init(N);
	for(int y = 0; y <= H; y++) for(int x = 0; x <= W; x++) f(y, x);
	run();
}

int swap_seats(int a, int b) {
	g(a, true); g(b, true);
	swap(C[A[a]][B[a]], C[A[b]][B[b]]);
	swap(A[a], A[b]); swap(B[a], B[b]);
	g(a); g(b);
	run();
	return seg.get();
}

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