Submission #569075

#	Time	Username	Problem	Language	Result	Execution time	Memory
569075		valerikk	Seats (IOI18_seats)	C++17	100 / 100	3888 ms	141532 KiB

seats

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

using namespace std;

struct SegTree {
	int n;
	vector<int> mn, cnt, delta;

	void apply(int v, int val) {
		mn[v] += val;
		delta[v] += val;
	}

	void push(int v) {
		apply(2 * v, delta[v]);
		apply(2 * v + 1, delta[v]);
		delta[v] = 0;
	}

	void pull(int v) {
		mn[v] = min(mn[2 * v], mn[2 * v + 1]);
		cnt[v] = (mn[2 * v] == mn[v] ? cnt[2 * v] : 0) + (mn[2 * v + 1] == mn[v] ? cnt[2 * v + 1] : 0);
	}

	void update(int v, int l, int r, int ql, int qr, int val) {
		if (l >= qr || r <= ql) 
			return;
		if (l >= ql && r <= qr) {
			apply(v, val);
			return;
		}
		
		push(v);
		
		int mid = (l + r) / 2;
		update(2 * v, l, mid, ql, qr, val);
		update(2 * v + 1, mid, r, ql, qr, val);

		pull(v);
	}

	void build(int v, int l, int r) {
		if (r - l == 1) {
			mn[v] = 0;
			cnt[v] = 1;
		} else {
			int mid = (l + r) / 2;
			build(2 * v, l, mid);
			build(2 * v + 1, mid, r);

			pull(v);
		}
	}

	int get(int need) {
		return mn[1] == need ? cnt[1] : 0;
	}

	SegTree() {}

	SegTree(int n) : n(n) {
		mn.resize(4 * n);
		cnt.resize(4 * n);
		delta.resize(4 * n);

		build(1, 0, n);
	}
};

const int N = 1e6 + 10;

int h, w, n;
int r[N], c[N];
vector<vector<int>> arr;
SegTree st;

void update(int x, int y, int delta) {
	vector<int> vals;
	for (int i = x; i <= x + 1; ++i) {
		for (int j = y; j <= y + 1; ++j) {
			vals.push_back(i >= 0 && i < h && j >= 0 && j < w ? arr[i][j] : n);
		}
	}
	sort(vals.begin(), vals.end());

	st.update(1, 0, n, vals[0], vals[1], delta);
	st.update(1, 0, n, vals[2], vals[3], delta);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h = H, w = W;
	
	n = h * w;

	arr.resize(h, vector<int>(w));
	for (int i = 0; i < h * w; ++i) {
		r[i] = R[i];
		c[i] = C[i];
		arr[r[i]][c[i]] = i;
	}

	st = {n};

	for (int x = -1; x < h; ++x) {
		for (int y = -1; y < w; ++y) {
			update(x, y, 1);
		}
	}
}

int swap_seats(int a, int b) {
	vector<pair<int, int>> changes;
	for (int i = r[a] - 1; i <= r[a]; ++i) {
		for (int j = c[a] - 1; j <= c[a]; ++j) {
			changes.push_back({i, j});
		}
	}
	for (int i = r[b] - 1; i <= r[b]; ++i) {
		for (int j = c[b] - 1; j <= c[b]; ++j) {
			changes.push_back({i, j});
		}
	}
	sort(changes.begin(), changes.end());
	changes.resize(unique(changes.begin(), changes.end()) - changes.begin());

	for (auto p : changes) {
		update(p.first, p.second, -1);
	}

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

	for (auto p : changes) {
		update(p.first, p.second, 1);
	}

	return st.get(4);
}

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