Submission #568148

#	Time	Username	Problem	Language	Result	Execution time	Memory
568148		valerikk	Seats (IOI18_seats)	C++17	31 / 100	4100 ms	227800 KiB

seats

#include "seats.h"
#include <set>
#include <algorithm>

using namespace std;

const int M = 1005;
const int N = 1e6 + 10;

int h, w;
int r[N], c[N];
set<int> sr[N], sc[N];

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];
	}

	for (int i = 0; i < h * w; ++i) {
		sr[r[i]].insert(i);
		sc[c[i]].insert(i);
	}
}

int swap_seats(int a, int b) {
	sr[r[a]].erase(a);
	sc[c[a]].erase(a);
	sr[r[b]].erase(b);
	sc[c[b]].erase(b);

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

	sr[r[a]].insert(a);
	sc[c[a]].insert(a);
	sr[r[b]].insert(b);
	sc[c[b]].insert(b);

	vector<pair<int, int>> v;

	for (int i = 0; i < h; ++i) {
		v.emplace_back(*sr[i].begin(), i + 1);
	}
	for (int i = 0; i < w; ++i) {
		v.emplace_back(*sc[i].begin(), -i - 1);
	}

	sort(v.begin(), v.end());

	int res = 0;

	int minr = h - 1, maxr = 0, minc = w - 1, maxc = 0;
	for (int i = 0; i < h + w; ++i) {
		if (v[i].second > 0) {
			minr = min(minr, v[i].second - 1);
			maxr = max(maxr, v[i].second - 1);
		} else {
			minc = min(minc, -v[i].second - 1);
			maxc = max(maxc, -v[i].second - 1);
		}

		if (i == h + w - 1 || v[i].first < v[i + 1].first) {
			int s = (maxr - minr + 1) * (maxc - minc + 1);

			if (s >= v[i].first + 1 && (i == h + w - 1 || s <= v[i + 1].first)) {
				++res;
			} 
		}
	}

	return res;
}

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