Submission #568149

#	Time	Username	Problem	Language	Result	Execution time	Memory
568149		valerikk	자리 배치 (IOI18_seats)	C++17	17 / 100	4082 ms	56360 KiB

seats

#include "seats.h"

using namespace std;

const int N = 1e6 + 7;

int h, w;
int r[N], c[N];
int minr[N], maxr[N], minc[N], maxc[N];
int res;

void upd(int i) {
	minr[i] = maxr[i] = r[i];
	minc[i] = maxc[i] = c[i];
	if (i != 0) {
		minr[i] = min(minr[i], minr[i - 1]);
		maxr[i] = max(maxr[i], maxr[i - 1]);
		minc[i] = min(minc[i], minc[i - 1]);
		maxc[i] = max(maxc[i], maxc[i - 1]);
	}
}

bool good(int i) {
	return (maxr[i] - minr[i] + 1) * (maxc[i] - minc[i] + 1) == i + 1;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h = H, w = W;

	for (int i = 0; i < h * w; ++i) {
		r[i] = R[i], c[i] = C[i];
	}

	res = 0;

	for (int i = 0; i < h * w; ++i) {
		upd(i);
		if (good(i)) {
			++res;
		}
	}
}

int swap_seats(int a, int b) {
	for (int i = min(a, b); i <= max(a, b); ++i) {
		if (good(i)) {
			--res;
		}
	}

	swap(r[a], r[b]);
	swap(c[a], c[b]);

	for (int i = min(a, b); i <= max(a, b); ++i) {
		upd(i);
		if (good(i)) {
			++res;
		}
	}

	return res;
}

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