Submission #1266811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266811		xnqs	Seats (IOI18_seats)	C++20	20 / 100	1778 ms	75364 KiB

seats

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>

#include "seats.h"

struct SegTreeNode {
	int min = 0x3f3f3f3f;
	int cnt = 1;
};

static SegTreeNode get_dummy_node() {
	static SegTreeNode _dummy_node = {
		.min = 0x3f3f3f3f,
		.cnt = 0,
	};
	return _dummy_node;
}

SegTreeNode combine(const SegTreeNode& a, const SegTreeNode& b) {
	SegTreeNode ret = {
		.min = std::min(a.min, b.min),
		.cnt = (a.min == b.min) ? a.cnt + b.cnt : (a.min < b.min) ? a.cnt : b.cnt,
	};
	return ret;
}

int h, w;
std::vector<std::vector<int>> arr;
std::vector<int> row;
std::vector<int> column;

std::vector<SegTreeNode> tree;
std::vector<int> lazy;

void build_tree(int node, int l, int r) {
	if (l == r) {
		tree[node] = {
			.min = 0,
			.cnt = 1,
		};
		return;
	}

	int m = (l+r) >> 1;
	build_tree(node<<1, l, m);
	build_tree(node<<1|1, m+1, r);
	tree[node] = combine(tree[node<<1], tree[node<<1|1]);
}

void push(int node, int l, int r) {
	tree[node].min += lazy[node];
	if (l != r) {
		lazy[node<<1] += lazy[node];
		lazy[node<<1|1] += lazy[node];
	}
	lazy[node] = 0;
}

void update(int node, int l, int r, int st, int fi, int add) {
	push(node, l, r);
	if (l > fi || r < st) {
		return;
	}
	if (st <= l && r <= fi) {
		lazy[node] += add;
		push(node, l, r);
		return;
	}

	int m = (l+r) >> 1;
	update(node<<1, l, m, st, fi, add);
	update(node<<1|1, m+1, r, st, fi, add);
	tree[node] = combine(tree[node<<1], tree[node<<1|1]);
}

SegTreeNode query(int node, int l, int r, int st, int fi) {
	push(node, l, r);
	if (l > fi || r < st) {
		return get_dummy_node();
	}
	if (st <= l && r <= fi) {
		return tree[node];
	}

	int m = (l+r) >> 1;
	return combine(query(node<<1, l, m, st, fi), query(node<<1|1, m+1, r, st, fi));
}

void add_delta(int l, int r, int add) {
	if (l < r) {
		update(1, 0, h*w-1, l, r-1, add);
	}
}

// We want the number of 2x2 grids that contain a single 1 + the ones that contain 3 ones = 4
void activate(int x, int y, int sgn) {
	int i = arr[x][y];

	// 1 0
	// 0 0
	add_delta(i, std::min({arr[x][y+1], arr[x+1][y], arr[x+1][y+1]}), sgn);
	// 2 less than it
	int less = 0;
	int max = 0;
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			less += (arr[x+i][y+j] < arr[x][y]);
			max = std::max(max, arr[x+i][y+j]);
		}
	}
	if (less == 2) {
		add_delta(i, max, sgn);
	}

	// 0 1
	// 0 0
	add_delta(i, std::min({arr[x][y-1], arr[x+1][y-1], arr[x+1][y]}), sgn);
	less = 0;
	max = 0;
	for (int i = 0; i <= 1; i++) {
		for (int j = -1; j <= 0; j++) {
			less += (arr[x+i][y+j] < arr[x][y]);
			max = std::max(max, arr[x+i][y+j]);
		}
	}
	if (less == 2) {
		add_delta(i, max, sgn);
	}

	// 0 0
	// 1 0
	add_delta(i, std::min({arr[x-1][y], arr[x-1][y+1], arr[x][y+1]}), sgn);
	less = 0;
	max = 0;
	for (int i = -1; i <= 0; i++) {
		for (int j = 0; j <= 1; j++) {
			less += (arr[x+i][y+j] < arr[x][y]);
			max = std::max(max, arr[x+i][y+j]);
		}
	}
	if (less == 2) {
		add_delta(i, max, sgn);
	}
	
	// 0 0
	// 0 1
	add_delta(i, std::min({arr[x-1][y-1], arr[x-1][y], arr[x][y-1]}), sgn);
	less = 0;
	max = 0;
	for (int i = -1; i <= 0; i++) {
		for (int j = -1; j <= 0; j++) {
			less += (arr[x+i][y+j] < arr[x][y]);
			max = std::max(max, arr[x+i][y+j]);
		}
	}
	if (less == 2) {
		add_delta(i, max, sgn);
	}
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h = H;
	w = W;
	arr.assign(H+2, std::vector<int>(W+2, H*W));
	row.assign(H*W, 0);
	column.assign(H*W, 0);
	tree.resize(4*H*W+1);
	lazy.assign(4*H*W+1, 0);

	for (int i = 0; i < H*W; i++) {
		arr[R[i]+1][C[i]+1] = i;
		row[i] = R[i]+1;
		column[i] = C[i]+1;
	}

#if 1
	build_tree(1, 0, H*W-1);
	for (int i = 0; i < H*W; i++) {
		int x = row[i];
		int y = column[i];
		activate(x, y, 1);
	}
#endif
}

// TODO
int swap_seats(int a, int b) {
	int xa = row[a];
	int ya = column[a];
	int xb = row[b];
	int yb = column[b];

	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if (1 <= xa+i && xa+i <= h && 1 <= ya+j && ya+j <= w) {
			  activate(xa+i, ya+j, -1);
			}
			if (1 <= xb+i && xb+i <= h && 1 <= yb+j && yb+j <= w) {
			  activate(xb+i, yb+j, -1);
			}
		}
	}

	std::swap(row[a], row[b]);
	std::swap(column[a], column[b]);
	std::swap(arr[xa][ya], arr[xb][yb]);
	
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if (1 <= xa+i && xa+i <= h && 1 <= ya+j && ya+j <= w) {
			  activate(xa+i, ya+j, 1);
			}
			if (1 <= xb+i && xb+i <= h && 1 <= yb+j && yb+j <= w) {
			  activate(xb+i, yb+j, 1);
			}
		}
	}
	
	/*for (int i = 0; i < h*w; i++) {
		std::cout << query(1, 0, h*w-1, i, i).min << " ";
	}
	std::cout << "\n";*/

	//std::cout << query(1, 0, h*w-1, 0, h*w-1).min << " " << query(1, 0, h*w-1, 0, h*w-1).cnt << "\n";
	return query(1, 0, h*w-1, 0, h*w-1).cnt;
}

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