Submission #593370

#	Time	Username	Problem	Language	Result	Execution time	Memory
593370		Temmie	Seats (IOI18_seats)	C++17	70 / 100	4070 ms	175292 KiB

seats

#include <bits/stdc++.h>

constexpr const int mxn = 1e6 + 3;

struct Seg {
	
	int size;
	int res[mxn << 2], min[mxn << 2], laz[mxn << 2];
	
	Seg() = default;
	
	Seg(int s) {
		memset(res, 0, sizeof(res));
		memset(min, 0, sizeof(min));
		memset(laz, 0, sizeof(laz));
		size = s;
		build(0, 0, size);
	}
	
	void build(int now, int l, int r) {
		if (!(r - l - 1)) {
			res[now] = 1;
			return;
		}
		int mid = (l + r) >> 1;
		build(now * 2 + 1, l, mid);
		build(now * 2 + 2, mid, r);
		res[now] = res[now * 2 + 1] + res[now * 2 + 2];
	}
	
	inline void push(int now, int l, int r) {
		min[now] += laz[now];
		if (r - l - 1) {
			laz[now * 2 + 1] += laz[now];
			laz[now * 2 + 2] += laz[now];
		}
		laz[now] = 0;
	}
	
	inline void update(int l, int r, int val) {
		if (r <= l) {
			return;
		}
		update(l, r, val, 0, 0, size);
	}
	
	void update(int tl, int tr, int val, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return;
		}
		if (l >= tl && r <= tr) {
			laz[now] += val;
			return;
		}
		push(now, l, r);
		int mid = (l + r) >> 1;
		update(tl, tr, val, now * 2 + 1, l, mid);
		update(tl, tr, val, now * 2 + 2, mid, r);
		push(now * 2 + 1, l, mid);
		push(now * 2 + 2, mid, r);
		min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
		res[now] =
		(min[now * 2 + 1] == min[now] ? res[now * 2 + 1] : 0) +
		(min[now * 2 + 2] == min[now] ? res[now * 2 + 2] : 0);
	}
	
	inline int query() {
		push(0, 0, size);
		return min[0] == 4 ? res[0] : 0;
	}
	
} seg;

int n, m;
std::vector <std::vector <int>> g;
std::pair <int, int> inv[mxn];

inline void fix(int i, int j, int val) {
	static int vals[4];
	for (int di = 0, ptr = 0; di <= 1; di++) {
		for (int dj = 0; dj <= 1; dj++) {
			vals[ptr++] = g[i + di][j + dj];
		}
	}
	std::sort(vals, vals + 4);
	seg.update(vals[0], vals[1], val);
	seg.update(vals[2], vals[3], val);
}

void give_initial_chart(int h, int w, std::vector <int> r, std::vector <int> c) {
	n = h;
	m = w;
	seg = Seg(n * m);
	g = std::vector <std::vector <int>> (n + 2, std::vector <int> (m + 2, n * m));
	for (int i = 0; i < n * m; i++) {
		inv[i] = { ++r[i], ++c[i] };
		g[r[i]][c[i]] = i;
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			fix(i, j, 1);
		}
	}
}

int swap_seats(int a, int b) {
	auto av = inv[a];
	auto bv = inv[b];
	for (int di = 0; di <= 1; di++) {
		for (int dj = 0; dj <= 1; dj++) {
			fix(av.first - di, av.second - dj, -1);
			fix(bv.first - di, bv.second - dj, -1);
		}
	}
	std::swap(g[av.first][av.second], g[bv.first][bv.second]);
	std::swap(inv[a], inv[b]);
	for (int di = 0; di <= 1; di++) {
		for (int dj = 0; dj <= 1; dj++) {
			fix(av.first - di, av.second - dj, 1);
			fix(bv.first - di, bv.second - dj, 1);
		}
	}
	return seg.query();
}

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