제출 #435740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435740		rainboy	자리 배치 (IOI18_seats)	C++11	70 / 100	4098 ms	84420 KiB

seats

#include "seats.h"

using namespace std;

const int N = 1000000, N_ = 1 << 20, SMALL = 1000, INF = 0x3f3f3f3f;	// N_ = pow2(ceil(log2(N)))

typedef vector<int> vi;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int aa[SMALL][SMALL], aa_[N];
int ii[N], jj[N], ii1[N], ii2[N], jj1[N], jj2[N];

void compute_prefix(int a) {
	ii1[a] = min(ii[a], a == 0 ? INF : ii1[a - 1]);
	ii2[a] = max(ii[a], a == 0 ? -1 : ii2[a - 1]);
	jj1[a] = min(jj[a], a == 0 ? INF : jj1[a - 1]);
	jj2[a] = max(jj[a], a == 0 ? -1 : jj2[a - 1]);
}

int row[SMALL], col[SMALL];
int n, m, cnt;

void compute_row(int i) {
	int j;

	row[i] = INF;
	for (j = 0; j < m; j++)
		row[i] = min(row[i], aa[i][j]);
}

void compute_col(int j) {
	int i;

	col[j] = INF;
	for (i = 0; i < n; i++)
		col[j] = min(col[j], aa[i][j]);
}

void solve_small() {
	static int ll[N], rr[N], uu[N], dd[N];
	int i, iu, id, j, jl, jr;

	for (i = 0; i < n; i++)
		uu[i] = min(row[i], i == 0 ? INF : uu[i - 1]);
	for (i = n - 1; i >= 0; i--)
		dd[i] = min(row[i], i + 1 == n ? INF : dd[i + 1]);
	for (j = 0; j < m; j++)
		ll[j] = min(col[j], j == 0 ? INF : ll[j - 1]);
	for (j = m - 1; j >= 0; j--)
		rr[j] = min(col[j], j + 1 == m ? INF : rr[j + 1]);
	iu = id = ii[0], jl = jr = jj[0], cnt = 1;
	while (1) {
		int t = INF;

		if (iu > 0)
			t = min(t, uu[iu - 1]);
		if (id + 1 < n)
			t = min(t, dd[id + 1]);
		if (jl > 0)
			t = min(t, ll[jl - 1]);
		if (jr + 1 < m)
			t = min(t, rr[jr + 1]);
		if (t == INF)
			break;
		if (t == (id - iu + 1) * (jr - jl + 1))
			cnt++;
		if (iu > 0 && uu[iu - 1] == t)
			iu--;
		if (id + 1 < n && dd[id + 1] == t)
			id++;
		if (jl > 0 && ll[jl - 1] == t)
			jl--;
		if (jr + 1 < m && rr[jr + 1] == t)
			jr++;
	}
}

int sum[N_ * 2], pref[N_ * 2], kk[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1, x, y;

	sum[i] = sum[l] + sum[r];
	x = pref[l], y = sum[l] + pref[r];
	if (x < y)
		pref[i] = x, kk[i] = kk[l];
	else if (x > y)
		pref[i] = y, kk[i] = kk[r];
	else
		pref[i] = x, kk[i] = kk[l] + kk[r];
}

void update(int i, int x) {
	i += n_;
	pref[i] = sum[i] += x;
	while (i > 1)
		pul(i >>= 1);
}

void give_initial_chart(int n1, int m_, vi ii_, vi jj_) {
	int i, j, a;

	n = n1, m = m_;
	for (a = 0; a < n * m; a++) {
		ii[a] = ii_[a], jj[a] = jj_[a], compute_prefix(a);
		if (n == 1)
			aa_[jj[a]] = a;
		else if (n <= SMALL && m <= SMALL)
			aa[ii[a]][jj[a]] = a;
		if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
			cnt++;
	}
	if (n == 1) {
		n_ = 1;
		while (n_ < m)
			n_ <<= 1;
		for (i = 0; i < n_; i++)
			if (i < m)
				sum[n_ + i] = pref[n_ + i] = 1, kk[n_ + i] = 1;
		for (i = n_ - 1; i > 0; i--)
			pul(i);
		for (i = 1; i < m; i++)
			update(max(aa_[i - 1], aa_[i]), -1);
	} else if (n <= SMALL && m <= SMALL) {
		for (i = 0; i < n; i++)
			compute_row(i);
		for (j = 0; j < m; j++)
			compute_col(j);
	}
}

int swap_seats(int l, int r) {
	int a, tmp;

	if (l > r)
		tmp = l, l = r, r = tmp;
	if (n == 1) {
		int i = jj[l], j = jj[r];

		if (i + 1 == j) {
			if (i > 0)
				update(max(aa_[i - 1], aa_[i]), 1);
			update(max(aa_[i], aa_[i + 1]), 1);
			if (i + 2 < m)
				update(max(aa_[i + 1], aa_[i + 2]), 1);
		} else if (j + 1 == i) {
			if (j > 0)
				update(max(aa_[j - 1], aa_[j]), 1);
			update(max(aa_[j], aa_[j + 1]), 1);
			if (j + 2 < m)
				update(max(aa_[j + 1], aa_[j + 2]), 1);
		} else {
			if (i > 0)
				update(max(aa_[i - 1], aa_[i]), 1);
			if (i + 1 < m)
				update(max(aa_[i], aa_[i + 1]), 1);
			if (j > 0)
				update(max(aa_[j - 1], aa_[j]), 1);
			if (j + 1 < m)
				update(max(aa_[j], aa_[j + 1]), 1);
		}
		aa_[i] = r, aa_[j] = l;
		if (i + 1 == j) {
			if (i > 0)
				update(max(aa_[i - 1], aa_[i]), -1);
			update(max(aa_[i], aa_[i + 1]), -1);
			if (i + 2 < m)
				update(max(aa_[i + 1], aa_[i + 2]), -1);
		} else if (j + 1 == i) {
			if (j > 0)
				update(max(aa_[j - 1], aa_[j]), -1);
			update(max(aa_[j], aa_[j + 1]), -1);
			if (j + 2 < m)
				update(max(aa_[j + 1], aa_[j + 2]), -1);
		} else {
			if (i > 0)
				update(max(aa_[i - 1], aa_[i]), -1);
			if (i + 1 < m)
				update(max(aa_[i], aa_[i + 1]), -1);
			if (j > 0)
				update(max(aa_[j - 1], aa_[j]), -1);
			if (j + 1 < m)
				update(max(aa_[j], aa_[j + 1]), -1);
		}
		tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
		cnt = kk[1];
	} else if (n <= SMALL && m <= SMALL) {
		tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
		aa[ii[l]][jj[l]] = l, aa[ii[r]][jj[r]] = r;
		compute_row(ii[l]), compute_row(ii[r]), compute_col(jj[l]), compute_col(jj[r]);
		solve_small();
	} else {
		tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
		for (a = l; a <= r; a++) {
			if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
				cnt--;
			compute_prefix(a);
			if ((ii2[a] - ii1[a] + 1) * (jj2[a] - jj1[a] + 1) == a + 1)
				cnt++;
		}
	}
	return cnt;
}

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