Submission #1235048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235048		colossal_pepe	Seats (IOI18_seats)	C++20	17 / 100	4094 ms	43828 KiB

seats

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

const int INF = 1e9;

int n, h, w, cnt_good;
vector<int> r, r_mn, r_mx, c, c_mn, c_mx, is_good;

int area(int i) {
	return (r_mx[i] - r_mn[i] + 1) * (c_mx[i] - c_mn[i] + 1);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H, w = W, n = H * W;
	r = R, r_mn = r, r_mx = r, c = C, c_mn = c, c_mx = c;
	is_good.resize(n);
	cnt_good = is_good[0] = 1;
	for (int i = 1; i < n; i++) {
		r_mn[i] = min(r_mn[i - 1], r[i]);
		r_mx[i] = max(r_mx[i - 1], r[i]);
		c_mn[i] = min(c_mn[i - 1], c[i]);
		c_mx[i] = max(c_mx[i - 1], c[i]);
		is_good[i] = (area(i) == i + 1);
		cnt_good += is_good[i];
	}
}

int swap_seats(int a, int b) {
	if (a > b) swap(a, b);
	if (b - a > 10000) cout << "parumna";
	for (int i = a; i <= b; i++) {
		cnt_good -= is_good[i];
	}
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for (int i = a; i <= b; i++) {
		r_mn[i] = min(i ? r_mn[i - 1] : INF, r[i]);
		r_mx[i] = max(i ? r_mx[i - 1] :  -1, r[i]);
		c_mn[i] = min(i ? c_mn[i - 1] : INF, c[i]);
		c_mx[i] = max(i ? c_mx[i - 1] :  -1, c[i]);
		is_good[i] = (area(i) == i + 1);
		cnt_good += is_good[i];
	}
	return cnt_good;
}

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