Submission #392812

#	Time	Username	Problem	Language	Result	Execution time	Memory
392812		JimmyZJX	Seats (IOI18_seats)	C++14	0 / 100	636 ms	231484 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;

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

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

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

	SegNode(int l, int r, SegNode* sub1, SegNode* sub2) {
		this->l = l; this->r = r;
		if (l == r) {
			maxV = max(sub1->maxV, sub2->maxV);
			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);
		}
	}

	SegNode(int l, int r, const Vi& row) {
		this->l = l; this->r = r;
		if (l == r) {
			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);
		}
	}
};

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

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

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

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

	while (curMax < hw - 1) {
		rect.expand(r[curMax + 1], c[curMax + 1]);

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

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

	return ans;
}

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

	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