Submission #768388

#	Time	Username	Problem	Language	Result	Execution time	Memory
768388		SanguineChameleon	Seats (IOI18_seats)	C++17	17 / 100	4021 ms	56404 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];
int N, H, W;
int cnt;

void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
	H = _H;
	W = _W;
	N = H * W;
	min_R[0] = H + 1;
	min_C[0] = W + 1;
	for (int i = 1; i <= N; i++) {
		R[i] = _R[i - 1] + 1;
		C[i] = _C[i - 1] + 1;
		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) {
	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: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30