제출 #435581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435581		rainboy	자리 배치 (IOI18_seats)	C++17	17 / 100	4050 ms	55364 KiB

seats

#include "seats.h"

using namespace std;

const int S = 1000000, 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 ii[S], jj[S], ii1[S], ii2[S], jj1[S], jj2[S];

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

int cnt;

void give_initial_chart(int n, int m, vi ii_, vi jj_) {
	int h;

	for (h = 0; h < n * m; h++) {
		ii[h] = ii_[h], jj[h] = jj_[h], compute(h);
		cnt += (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
	}
}

int swap_seats(int l, int r) {
	int h, 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;
	for (h = l; h <= r; h++) {
		cnt -= (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
		compute(h);
		cnt += (jj2[h] - jj1[h] + 1) * (ii2[h] - ii1[h] + 1) == h + 1;
	}
  return cnt;
}

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