Submission #654325

#	Time	Username	Problem	Language	Result	Execution time	Memory
654325		buidangnguyen05	Seats (IOI18_seats)	C++14	17 / 100	4083 ms	77648 KiB

seats

//source:

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

typedef long long ll;
const int N = 1e6 + 10;
int row[N], col[N], ans[N];

int res;
bool sub4 = 1;

int n, m, q;
vector<pair<int, int>> query;

struct SegmentTree {
	int mx[4 * N], mi[4 * N];

	void up(int s, int l, int r, int pos, int val) {
		if (l == r) {
			mx[s] = mi[s] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) up(s << 1, l, mid, pos, val);
		else up(s << 1 | 1, mid + 1, r, pos, val);
		mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
		mi[s] = min(mi[s << 1], mi[s << 1 | 1]);
	}

	pair<int, int> get(int s, int l, int r, int u, int v) {
		if (l > v || r < u || u > v) return make_pair(1e9, 0);
		if (l >= u && r <= v) return make_pair(mi[s], mx[s]);
		int mid = (l + r) >> 1;
		pair<int, int> L = get(s << 1, l, mid, u, v), R = get(s << 1 | 1, mid + 1, r, u, v);
		return make_pair(min(L.first, R.first), max(L.second, R.second));
	}
} R, C;

int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	++x; ++y;

	if (sub4 && y - x <= 1e4) {
		R.up(1, 1, m * n, x, row[y]);
		R.up(1, 1, m * n, y, row[x]);

		C.up(1, 1, m * n, x, col[y]);
		C.up(1, 1, m * n, y, col[x]);

		swap(row[x], row[y]); swap(col[x], col[y]);

		int miR, mxR, miC, mxC;
		tie(miR, mxR) = R.get(1, 1, m * n, 1, x - 1); tie(miC, mxC) = C.get(1, 1, m * n, 1, x - 1);

		for (int i = x; i <= y; ++i) {
			mxR = max(mxR, row[i]);
			miR = min(miR, row[i]);
			mxC = max(mxC, col[i]);
			miC = min(miC, col[i]);

			int nans = (mxR - miR + 1) * (mxC - miC + 1) == i;

			res += nans - ans[i];
			ans[i] = nans;
		}
		return res;
	}
	else {
		sub4 = 0;

		R.up(1, 1, m * n, x, row[y]);
		R.up(1, 1, m * n, y, row[x]);

		C.up(1, 1, m * n, x, col[y]);
		C.up(1, 1, m * n, y, col[x]);

		swap(row[x], row[y]); swap(col[x], col[y]);

		int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9; res = 0;
		for (int i = 1; i <= m * n; ++i) {
			tie(miR, mxR) = R.get(1, 1, m * n, 1, i); tie(miC, mxC) = C.get(1, 1, m * n, 1, i);

			if ((mxR - miR + 1) * (mxC - miC + 1) == i) ++res;
			else i = (mxR - miR + 1) * (mxC - miC + 1) - 1;
		}
		return res;
	}
}

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C) {
	m = H, n = W;
	for (int i = 1; i <= m * n; ++i) {
		row[i] = _R[i - 1]; col[i] = _C[i - 1];
		++row[i]; ++col[i];
	}

	for (int i = 1; i <= m * n; ++i) {
		R.up(1, 1, m * n, i, row[i]);
		C.up(1, 1, m * n, i, col[i]);
	}

	for (int i = 1; i <= m * n; ++i) {
		R.up(1, 1, m * n, i, row[i]);
		C.up(1, 1, m * n, i, col[i]);
	}

	int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9;
	for (int i = 1; i <= m * n; ++i) {
		mxR = max(mxR, row[i]);
		miR = min(miR, row[i]);
		mxC = max(mxC, col[i]);
		miC = min(miC, col[i]);

		if ((mxR - miR + 1) * (mxC - miC + 1) == i) ans[i] = 1, ++res;
	}
}

// ඞඞඞඞඞ you sus

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