Submission #392815

#	Time	Username	Problem	Language	Result	Execution time	Memory
392815		JimmyZJX	Seats (IOI18_seats)	C++14	0 / 100	4078 ms	215452 KiB

seats

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)


int h, w, hw;
Vi r, c;
Vii t;


struct SegNode {
	int l, r;
	SegNode* left, * right;
	int maxV, minV;

	int GetMax(int f, int t) { // [f, t]
		if (r < f || t < l) return 0;
		if (f <= l && r <= t) return maxV;

		return max(left->GetMax(f, t), right->GetMax(f, t));
	}

	int GetMin(int f, int t) { // [f, t]
		if (r < f || t < l) return 0;
		if (f <= l && r <= t) return minV;

		return min(left->GetMin(f, t), right->GetMin(f, t));
	}

	void update(int t, int v) {
		if (l <= t && t <= r) {
			if (l == r) {
				minV = maxV = v;
			} else {
				left->update(t, v);
				right->update(t, v);
				maxV = max(left->maxV, right->maxV);
				minV = min(left->minV, right->minV);
			}
		}
	}

	void update(int t, SegNode* sub1, SegNode* sub2) {
		if (l <= t && t <= r) {
			if (l == r) {
				maxV = max(sub1->maxV, sub2->maxV);
				minV = min(sub1->minV, sub2->minV);
			} else {
				left->update(t, sub1->left, sub2->left);
				right->update(t, sub1->right, sub2->right);
				maxV = max(left->maxV, right->maxV);
				minV = min(left->minV, right->minV);
			}
		}
	}

	SegNode(int l, int r, SegNode* sub1, SegNode* sub2) {
		this->l = l; this->r = r;
		if (l == r) {
			maxV = max(sub1->maxV, sub2->maxV);
			minV = min(sub1->minV, sub2->minV);
			left = right = nullptr;
		} else {
			int mid = (l + r) / 2;
			left = new SegNode(l, mid, sub1->left, sub2->left);
			right = new SegNode(mid + 1, r, sub1->right, sub2->right);
			maxV = max(left->maxV, right->maxV);
			minV = min(left->minV, right->minV);
		}
	}

	SegNode(int l, int r, const Vi& row) {
		this->l = l; this->r = r;
		if (l == r) {
			minV = maxV = row[l];
			left = right = nullptr;
		} else {
			int mid = (l + r) / 2;
			left = new SegNode(l, mid, row);
			right = new SegNode(mid + 1, r, row);
			maxV = max(left->maxV, right->maxV);
			minV = min(left->minV, right->minV);
		}
	}
};

struct SegRow {
	int l, r;
	SegRow* left, * right;
	SegNode* rowRoot;

	int GetMax(int f, int t, int yl, int yr) { // [f, t]
		if (r < f || t < l) return 0;
		if (f <= l && r <= t) return rowRoot->GetMax(yl, yr);

		return max(left->GetMax(f, t, yl, yr), right->GetMax(f, t, yl, yr));
	}

	int GetMin(int f, int t, int yl, int yr) { // [f, t]
		if (r < f || t < l) return 0;
		if (f <= l && r <= t) return rowRoot->GetMin(yl, yr);

		return min(left->GetMin(f, t, yl, yr), right->GetMin(f, t, yl, yr));
	}

	void update(int row, int col) {
		if (l <= row && row <= r) {
			if (l == r) {
				rowRoot->update(col, t[row][col]);
			} else {
				left->update(row, col);
				right->update(row, col);
				rowRoot->update(col, left->rowRoot, right->rowRoot);
			}
		}
	}

	SegRow(int l, int r) {
		this->l = l; this->r = r;
		if (l == r) {
			rowRoot = new SegNode(0, w - 1, t[l]);
			left = right = nullptr;
		} else {
			int mid = (l + r) / 2;
			left = new SegRow(l, mid);
			right = new SegRow(mid + 1, r);
			rowRoot = new SegNode(0, w - 1, left->rowRoot, right->rowRoot);
		}
	}
};

SegRow* root;

void give_initial_chart(int H, int W, Vi R, Vi C) {
	h = H, w = W, hw = H * W;
	r = R, c = C;
	t = Vii(h, Vi(w));

	forR(i, hw) {
		t[R[i]][C[i]] = i;
	}

	root = new SegRow(0, h - 1);
}

struct Rect {
	int x1, x2, y1, y2;

	void expand(int x, int y) {
		x1 = min(x1, x);
		x2 = max(x2, x);
		y1 = min(y1, y);
		y2 = max(y2, y);
	}

	int area() {
		return (x2 - x1 + 1) * (y2 - y1 + 1);
	}

	vector<Rect> surroundings() {
		vector<Rect> r;
		if (x1 > 0)     r.push_back(Rect{ 0, x1 - 1, 0, w - 1 });
		if (x2 < h - 1) r.push_back(Rect{ x2 + 1, h - 1, 0, w - 1 });
		if (y1 > 0)     r.push_back(Rect{ 0, h - 1, 0, y1 - 1 });
		if (y2 < w - 1) r.push_back(Rect{ 0, h - 1, y2 + 1, w - 1 });
		return r;
	}
};

int swap_seats(int a, int b) {
	swap(t[r[a]][c[a]], t[r[b]][c[b]]);
	swap(r[a], r[b]); swap(c[a], c[b]);

	root->update(r[a], c[a]); root->update(r[b], c[b]);

#ifdef TEST_LOCAL
	// test
	forR(x1, h) forR(y1, w)
		for (int x2 = x1; x2 < h; x2++)
			for (int y2 = y1; y2 < w; y2++) {
				int maxV = 0;
				for (int x = x1; x <= x2; x++)
					for (int y = y1; y <= y2; y++) {
						maxV = max(maxV, t[x][y]);
					}
				assert(maxV == root->GetMax(x1, x2, y1, y2));
			}

#endif

	int ans = 1;
	Rect rect{ r[0],r[0], c[0],c[0] };

	while (true) {
		auto sur = rect.surroundings();
		int minNext = hw;
		for (auto& re : sur) {
			minNext = min(minNext, root->GetMin(re.x1, re.x2, re.y1, re.y2));
		}

		rect.expand(r[minNext], c[minNext]);

		int curMax = root->GetMax(rect.x1, rect.x2, rect.y1, rect.y2);

		if (rect.area() == curMax + 1) ans++;
		if (curMax == hw - 1) break;
	}

	return ans;
}

#ifdef TEST_LOCAL
int main() {
	give_initial_chart(3, 3, Vi{ 0, 1, 1, 0, 0, 1, 2, 2, 2 }, Vi{ 0, 0, 1, 1, 2, 2, 0, 1, 2 });

	srand(0);
	forR(r, 1000000) {
		swap_seats(rand() % 9, rand() % 9);
	}
	int r = swap_seats(0, 5);
	r = swap_seats(0, 5);

	return 0;
}
#endif

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