Submission #1235008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235008		colossal_pepe	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	86580 KiB

seats

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

// H, W <= 1000

const int INF = 1001;

struct SGT {
	int sz, null_val;
	function<int(int, int)> merge;
	vector<int> t;

	SGT(int _sz, int _null_val, function<int(int, int)> _merge) : sz(_sz), null_val(_null_val), merge(_merge) {
		t.resize(4 * sz, null_val);
	}

	void update(int v, int l, int r, int i, int x) {
		if (l == r) t[v] = x;
		else {
			int mid = (l + r) / 2;
			if (i <= mid) update(2 * v, l, mid, i, x);
			else update(2 * v + 1, mid + 1, r, i, x);
			t[v] = merge(t[2 * v], t[2 * v + 1]);
		}
	}
	void update(int i, int x) { update(1, 0, sz - 1, i, x); }

	int query(int v, int l, int r, int L, int R) {
		if (r < L or R < l) return null_val;
		else if (L <= l and r <= R) return t[v];
		else {
			int mid = (l + r) / 2;
			return merge(query(2 * v, l, mid, L, R), query(2 * v + 1, mid + 1, r, L, R));
		}
	}
	int query(int l, int r) { return query(1, 0, sz - 1, l, r); }
};

int n, h, w;
vector<int> r, c;
SGT *row_min, *row_max, *col_min, *col_max;

void updateAllSGT(int i, int r, int c) {
	row_min->update(i, r);
	row_max->update(i, r);
	col_min->update(i, c);
	col_max->update(i, c);
}

int area(int i) {
	int w_cur = row_max->query(0, i) - row_min->query(0, i) + 1;
	int h_cur = col_max->query(0, i) - col_min->query(0, i) + 1;
	return w_cur * h_cur;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	if (H > 1000 or W > 1000) cout << "parumna" << endl;
	h = H, w = W, n = H * W;
	r = R, c = C;
	row_min = new SGT(n, INF, [](int a, int b) { return min(a, b); });
	row_max = new SGT(n, -1, [](int a, int b) { return max(a, b); });
	col_min = new SGT(n, INF, [](int a, int b) { return min(a, b); });
	col_max = new SGT(n, -1, [](int a, int b) { return max(a, b); });
	for (int i = 0; i < n; i++) {
		updateAllSGT(i, r[i], c[i]);
	}
}

int swap_seats(int a, int b) {
	updateAllSGT(a, r[b], c[b]);
	updateAllSGT(b, r[a], c[a]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	int ans = 0, i = 0;
	while (i < n) {
		int a = area(i);
		ans += (a == i + 1);
		i = (a == i + 1 ? i + 1 : a - 1);
	}
	return ans;
}

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