Submission #820543

#	Time	Username	Problem	Language	Result	Execution time	Memory
820543		pavement	Seats (IOI18_seats)	C++17	100 / 100	1731 ms	187104 KiB

seats

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

#define mp make_pair

using ii = pair<int, int>;

int H, W;
vector<int> R, C, delta;
vector<vector<int> > grid;

int cell(int r, int c, int v) {
	if (!(-1 <= r && r < H && -1 <= c && c < W)) return 0;
	int ret = 0;
	for (int dr : {0, 1}) {
		for (int dc : {0, 1}) {
			int nr = r + dr, nc = c + dc;
			if (0 <= nr && nr < H && 0 <= nc && nc < W && grid[nr][nc] <= v) {
				ret++;
			}
		}
	}
	return ret;
}

struct node {
	node *left, *right;
	int S, E, sum;
	ii val;
	void combine() {
		assert(S != E);
		auto right_val = right->val;
		right_val.first += left->sum;
		sum = left->sum + right->sum;
		if (left->val.first == right_val.first) {
			val = mp(left->val.first, left->val.second + right_val.second);
		} else {
			val = min(left->val, right_val);
		}
	}
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			sum = val.first = delta[S];
			val.second = 1;
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		combine();
	}
	void upd(int p) {
		if (S == E) {
			sum = val.first = delta[S];
			val.second = 1;
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) left->upd(p);
		else right->upd(p);
		combine();
	}
} *root;

void upd(int x) {
	delta[x] = 0;
	for (int dr : {-1, 0}) {
		for (int dc : {-1, 0}) {
			int nr = R[x] + dr, nc = C[x] + dc, tmp = cell(nr, nc, x - 1);
			if (tmp == 1 || tmp == 3) {
				delta[x]--;
			}
		}
	}
	for (int dr : {-1, 0}) {
		for (int dc : {-1, 0}) {
			int nr = R[x] + dr, nc = C[x] + dc, tmp = cell(nr, nc, x);
			if (tmp == 1 || tmp == 3) {
				delta[x]++;
			}
		}
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	::H = H;
	::W = W;
	::R = R;
	::C = C;
	delta.resize(H * W);
	::grid = vector<vector<int> >(H, vector<int>(W, 0));
	for (int i = 0; i < H * W; i++) {
		grid[R[i]][C[i]] = i;
	}
	for (int i = 0; i < H * W; i++) {
		upd(i);
	}
	root = new node(0, H * W - 1);
}

int swap_seats(int a, int b) {
	swap(grid[R[a]][C[a]], grid[R[b]][C[b]]);
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	for (int dx = -1; dx <= 1; dx++) {
		for (int c : {a, b}) {
			int nc = c + dx;
			if (0 <= nc && nc < H * W) {
				upd(nc);
				root->upd(nc);
			}
		}
	}
	for (auto [r, c] : {mp(R[a], C[a]), mp(R[b], C[b])}) {
		for (int dr = -1; dr <= 1; dr++) {
			for (int dc = -1; dc <= 1; dc++) {
				int nr = r + dr, nc = c + dc;
				if (0 <= nr && nr < H && 0 <= nc && nc < W) {
					upd(grid[nr][nc]);
					root->upd(grid[nr][nc]);
				}
			}
		}
	}
	return root->val.second;
}

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