제출 #435732

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

seats

#include "seats.h"

using namespace std;

const int N = 1000000, SMALL = 1000, INF = 0x3f3f3f3f;

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];
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++;
	}
}

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

	n = n_, m = m_;
	for (a = 0; a < n * m; a++) {
		ii[a] = ii_[a], jj[a] = jj_[a], compute_prefix(a);
		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 <= 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;
	tmp = ii[l], ii[l] = ii[r], ii[r] = tmp, tmp = jj[l], jj[l] = jj[r], jj[r] = tmp;
	if (n <= SMALL && m <= SMALL) {
		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 {
		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: 0 / 33
• Subtask 6: 0 / 30