Submission #1135323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135323		alterio	Seats (IOI18_seats)	C++20	31 / 100	4090 ms	86864 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 1e6 + 100;

int n, h, w;
vector<int> r, c;

struct Node {
	int mxX = -1e7, mnX = 1e7, mxY = -1e7, mnY = 1e7;

	Node operator + (Node a) {
		return {max(mxX, a.mxX), min(mnX, a.mnX), max(mxY, a.mxY), min(mnY, a.mnY)};
	}
} null;

struct SGT {

	vector<Node> sgt;

	SGT(int sz) {
		sgt.resize(4 * sz);
	}

	void update(int k, int l, int r, int i, int x, int y) {
		if (l > i || r < i) return;
		if (l == r) {
			sgt[k] = {x, x, y, y};
			return;
		}
		int mid = (l + r) / 2;
		update(k * 2, l, mid, i, x, y);
		update(k * 2 + 1, mid + 1, r, i, x, y);
		sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
	}

	Node get(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return null;
		if (i <= l && r <= j) return sgt[k];
		int mid = (l + r) / 2 ;
		return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
	}

} sgt(mxn);

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H, w = W, r = R, c = C;
	n = h * w;
	for (int i = 0; i < n; i++) sgt.update(1, 0, n - 1, i, r[i], c[i]);
}

int swap_seats(int a, int b) {  
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	sgt.update(1, 0, n - 1, a, r[a], c[a]);
	sgt.update(1, 0, n - 1, b, r[b], c[b]);
	int ind = 0, ans = 0;
	while (ind < n) {
		Node get = sgt.get(1, 0, n - 1, 0, ind);
		int area = (get.mxX - get.mnX + 1) * (get.mxY - get.mnY + 1);
		if (area == ind + 1) ans++;
		ind = max(ind + 1, area - 1);
	}
	return ans;
}

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