Submission #1054876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054876		MinaRagy06	Seats (IOI18_seats)	C++17	17 / 100	4033 ms	60468 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int N = 1'000'005;
int mnr[N], mxr[N], mnc[N], mxc[N], gud[N], cnt = 0;
int n, m;
vector<int> r, c;
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
	n = _n, m = _m;
	r = _r, c = _c;
	mnr[0] = 1e9;
	mxr[0] = -1;
	mnc[0] = 1e9;
	mxc[0] = -1;
	for (int i = 0; i < n * m; i++) {
		mnr[i + 1] = min(mnr[i], r[i]);
		mxr[i + 1] = max(mxr[i], r[i]);

		mnc[i + 1] = min(mnc[i], c[i]);
		mxc[i + 1] = max(mxc[i], c[i]);
		gud[i] = (mxr[i + 1] - mnr[i + 1] + 1) * (mxc[i + 1] - mnc[i + 1] + 1) == i + 1;
		cnt += gud[i];
	}
}

int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	for (int i = x; i <= y; i++) {
		cnt -= gud[i];
		gud[i] = 0;
	}
	swap(r[x], r[y]);
	swap(c[x], c[y]);
	for (int i = x; i <= y; i++) {
		mnr[i + 1] = min(mnr[i], r[i]);
		mxr[i + 1] = max(mxr[i], r[i]);

		mnc[i + 1] = min(mnc[i], c[i]);
		mxc[i + 1] = max(mxc[i], c[i]);
		gud[i] = (mxr[i + 1] - mnr[i + 1] + 1) * (mxc[i + 1] - mnc[i + 1] + 1) == i + 1;
		cnt += gud[i];
	}
	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