Submission #820525

#	Time	Username	Problem	Language	Result	Execution time	Memory
820525		pavement	Seats (IOI18_seats)	C++17	0 / 100	4062 ms	138372 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);
	for (int i : delta) {
		cout << i << ' ';
	}
	cout << '\n';
}

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 i = 0; i < H * W; i++) {
		upd(i);
		root->upd(i);
	}
	//~ for (int dx = -1; dx <= 1; dx++) {
		//~ if (0 <= a + dx && a + dx < H * W) {
			//~ upd(a + dx);
			//~ root->upd(a + dx);
		//~ }
		//~ if (0 <= b + dx && b + dx < H * W) {
			//~ upd(b + dx);
			//~ root->upd(b + dx);
		//~ }
	//~ }
	//~ for (int i : delta) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	return root->val.second;
}

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