Submission #768401

#	Time	Username	Problem	Language	Result	Execution time	Memory
768401		SanguineChameleon	Seats (IOI18_seats)	C++17	37 / 100	4054 ms	173448 KiB

seats

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

const int maxN = 1e6 + 20;

struct node {
	int maxR, minR, maxC, minC;

	node(): maxR(0), minR(0), maxC(0), minC(0) {};

	node(int _maxR, int _minR, int _maxC, int _minC): maxR(_maxR), minR(_minR), maxC(_maxC), minC(_minC) {};
};

node merge(node left, node right) {
	return node(max(left.maxR, right.maxR), min(left.minR, right.minR), max(left.maxC, right.maxC), min(left.minC, right.minC));
}

node tree[maxN * 4];
int maxR[maxN];
int minR[maxN];
int maxC[maxN];
int minC[maxN];
int R[maxN];
int C[maxN];
priority_queue<int, vector<int>, greater<int>> posR[maxN];
priority_queue<int, vector<int>, greater<int>> posC[maxN];
int N, H, W;
int cnt;
bool sub3;

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = node(R[lt], R[lt], C[lt], C[lt]);
		return;
	}
	int mt = (lt + rt) >> 1;
	build(id << 1, lt, mt);
	build(id << 1 | 1, mt + 1, rt);
	tree[id] = merge(tree[id << 1], tree[id << 1 | 1]);
}

void update(int id, int lt, int rt, int pos) {
	if (lt == rt) {
		tree[id] = node(R[lt], R[lt], C[lt], C[lt]);
		return;
	}
	int mt = (lt + rt) >> 1;
	if (pos <= mt) {
		update(id << 1, lt, mt, pos);
	}
	else {
		update(id << 1 | 1, mt + 1, rt, pos);
	}
	tree[id] = merge(tree[id << 1], tree[id << 1 | 1]);
}

node get(int id, int lt, int rt, int pos) {
	if (lt == rt) {
		return tree[id];
	}
	int mt = (lt + rt) >> 1;
	if (pos <= mt) {
		return get(id << 1, lt, mt, pos);
	}
	else {
		return merge(tree[id << 1], get(id << 1 | 1, mt + 1, rt, pos));
	}
};

void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
	H = _H;
	W = _W;
	N = H * W;
	sub3 = (H <= 1000 && W <= 1000);
	for (int i = 1; i <= N; i++) {
		R[i] = _R[i - 1] + 1;
		C[i] = _C[i - 1] + 1;
	}
	if (sub3) {
		for (int i = 1; i <= N; i++) {
			posR[R[i]].push(i);
			posC[C[i]].push(i);
		}
		build(1, 1, N);
	}
	else {
		minR[0] = H + 1;
		minC[0] = W + 1;
		for (int i = 1; i <= N; i++) {
			maxR[i] = max(R[i], maxR[i - 1]);
			minR[i] = min(R[i], minR[i - 1]);
			maxC[i] = max(C[i], maxC[i - 1]);
			minC[i] = min(C[i], minC[i - 1]);
			if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
				cnt++;
			}
		}
	}
}

int swap_seats(int a, int b) {
	if (sub3) {
		a++;
		b++;
		swap(R[a], R[b]);
		swap(C[a], C[b]);
		update(1, 1, N, a);
		update(1, 1, N, b);
		posR[R[a]].push(a);
		posC[C[a]].push(a);
		posR[R[b]].push(b);
		posC[C[b]].push(b);
		priority_queue<int> cands;
		for (int i = 1; i <= H; i++) {
			int pos = -1;
			while (pos == -1 && !posR[i].empty()) {
				if (R[posR[i].top()] == i) {
					pos = posR[i].top();
					break;
				}
				else {
					posR[i].pop();
				}
			}
			if (pos > 1) {
				cands.push(pos - 1);
			}
		}
		for (int i = 1; i <= W; i++) {
			int pos = -1;
			while (pos == -1 && !posC[i].empty()) {
				if (C[posC[i].top()] == i) {
					pos = posC[i].top();
					break;
				}
				else {
					posC[i].pop();
				}
			}
			if (pos > 1) {
				cands.push(pos - 1);
			}
		}
		int pos = -1;
		cnt = 1;
		while (!cands.empty()) {
			if (cands.top() != pos) {
				pos = cands.top();
				node bounds = get(1, 1, N, pos);
				if ((bounds.maxR - bounds.minR + 1) * (bounds.maxC - bounds.minC + 1) == pos) {
					cnt++;
				}
			}
			cands.pop();
		}
		return cnt;
	}
	else {
		a++;
		b++;
		if (a > b) {
			swap(a, b);
		}
		for (int i = a; i <= b; i++) {
			if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
				cnt--;
			}
		}
		swap(R[a], R[b]);
		swap(C[a], C[b]);
		for (int i = a; i <= b; i++) {
			maxR[i] = max(R[i], maxR[i - 1]);
			minR[i] = min(R[i], minR[i - 1]);
			maxC[i] = max(C[i], maxC[i - 1]);
			minC[i] = min(C[i], minC[i - 1]);
			if ((maxR[i] - minR[i] + 1) * (maxC[i] - minC[i] + 1) == i) {
				cnt++;
			}
		}
		return cnt;
	}
}

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