Submission #768399

#	Time	Username	Problem	Language	Result	Execution time	Memory
768399		SanguineChameleon	Seats (IOI18_seats)	C++17	11 / 100	4078 ms	103100 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 20;
int max_R[maxN];
int min_R[maxN];
int max_C[maxN];
int min_C[maxN];
int R[maxN];
int C[maxN];
priority_queue<int, vector<int>, greater<int>> pos_R[maxN];
priority_queue<int, vector<int>, greater<int>> pos_C[maxN];
int N, H, W;
int cnt;
bool sub3;

void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
	H = _H;
	W = _W;
	N = H * W;
	sub3 = (H <= 1000 && W <= 1000);
	for (int i = 1; i <= N; i++) {
		R[i] = _R[i - 1] + 1;
		C[i] = _C[i - 1] + 1;
	}
	if (sub3) {
		for (int i = 1; i <= N; i++) {
			pos_R[R[i]].push(i);
			pos_C[C[i]].push(i);
		}
	}
	else {
		min_R[0] = H + 1;
		min_C[0] = W + 1;
		for (int i = 1; i <= N; i++) {
			max_R[i] = max(R[i], max_R[i - 1]);
			min_R[i] = min(R[i], min_R[i - 1]);
			max_C[i] = max(C[i], max_C[i - 1]);
			min_C[i] = min(C[i], min_C[i - 1]);
			if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
				cnt++;
			}
		}
	}
}

int swap_seats(int a, int b) {
	if (sub3) {
		a++;
		b++;
		swap(R[a], R[b]);
		swap(C[a], C[b]);
		min_R[0] = H + 1;
		min_C[0] = W + 1;
		for (int i = 1; i <= N; i++) {
			max_R[i] = max(R[i], max_R[i - 1]);
			min_R[i] = min(R[i], min_R[i - 1]);
			max_C[i] = max(C[i], max_C[i - 1]);
			min_C[i] = min(C[i], min_C[i - 1]);
		}
		pos_R[R[a]].push(a);
		pos_C[C[a]].push(a);
		pos_R[R[b]].push(b);
		pos_C[C[b]].push(b);
		priority_queue<int> cands;
		for (int i = 1; i <= H; i++) {
			int pos = -1;
			while (pos == -1 && !pos_R[i].empty()) {
				if (R[pos_R[i].top()] == i) {
					pos = pos_R[i].top();
					break;
				}
				else {
					pos_R[i].pop();
				}
			}
			if (pos > 1) {
				cands.push(pos - 1);
			}
		}
		for (int i = 1; i <= W; i++) {
			int pos = -1;
			while (pos == -1 && !pos_C[i].empty()) {
				if (C[pos_C[i].top()] == i) {
					pos = pos_C[i].top();
					break;
				}
				else {
					pos_C[i].pop();
				}
			}
			if (pos > 1) {
				cands.push(pos - 1);
			}
		}
		int pos = -1;
		cnt = 1;
		while (!cands.empty()) {
			if (cands.top() != pos) {
				pos = cands.top();
				if ((max_R[pos] - min_R[pos] + 1) * (max_C[pos] - min_C[pos] + 1) == pos) {
					cnt++;
				}
			}
			cands.pop();
		}
		return cnt;
	}
	else {
		a++;
		b++;
		if (a > b) {
			swap(a, b);
		}
		for (int i = a; i <= b; i++) {
			if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
				cnt--;
			}
		}
		swap(R[a], R[b]);
		swap(C[a], C[b]);
		for (int i = a; i <= b; i++) {
			max_R[i] = max(R[i], max_R[i - 1]);
			min_R[i] = min(R[i], min_R[i - 1]);
			max_C[i] = max(C[i], max_C[i - 1]);
			min_C[i] = min(C[i], min_C[i - 1]);
			if ((max_R[i] - min_R[i] + 1) * (max_C[i] - min_C[i] + 1) == i) {
				cnt++;
			}
		}
		return cnt;
	}
}

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