Submission #76334

#	Time	Username	Problem	Language	Result	Execution time	Memory
76334		arock	Seats (IOI18_seats)	C++14	100 / 100	3633 ms	103612 KiB

seats

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

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

struct seg {
	int min, ans;
} tree[4 * 1000 * 1000];
int lazy[4 * 1000 * 1000];
vector<vector<int>> RC;

seg merge(seg a, seg b) {
	if (a.min < b.min) {
		return a;
	} else if(b.min < a.min) {
		return b;
	} else {
		return {a.min, a.ans + b.ans};
	}
}

seg build(int cur, int lo, int hi) {
	if (lo == hi) {
		return tree[cur] = {0, 1};
	}

	int lmid = (lo + hi) / 2, rmid = lmid + 1;
	return tree[cur] = merge(build(cur << 1 | 0, lo, lmid),
		                     build(cur << 1 | 1, rmid, hi));
}

void update(int l, int r, int delta, int cur, int lo, int hi) {

	if (lo == l && hi == r) {
		lazy[cur]     += delta;
		tree[cur].min += delta;
	} else {

		lazy[cur << 1 | 0]     += lazy[cur];
		tree[cur << 1 | 0].min += lazy[cur];
		lazy[cur << 1 | 1]     += lazy[cur];
		tree[cur << 1 | 1].min += lazy[cur];
		lazy[cur] = 0;

		int lmid = (lo + hi) / 2, rmid = lmid + 1;
		if (l <= lmid) {
			update(l, min(r, lmid), delta, cur << 1 | 0, lo, lmid);
		}
		if (r >= rmid) {
			update(max(l, rmid), r, delta, cur << 1 | 1, rmid, hi);
		}

		tree[cur] = merge(tree[cur << 1 | 0],
			              tree[cur << 1 | 1]);
	}
}

void update(int l, int r, int delta) {
	if (l < r)
		update(l + 1, r, delta, 1, 1, H * W);
}

void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {

	H = HH, W = WW, R = RR, C = CC;

	RC = vector<vector<int>>(H + 2, vector<int>(W + 2, H * W));
	for (int i = 0; i < H * W; i++) {
		RC[R[i] + 1][C[i] + 1] = i;
	}

	build(1, 1, H * W);

	for (int i = 0; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			int adj[4] = {RC[i][j], RC[i][j + 1], RC[i + 1][j], RC[i + 1][j + 1]};
			sort(adj, adj + 4);

			update(adj[0], adj[1], +1);
			update(adj[2], adj[3], +1);
		}
	}
}


int swap_seats(int a, int b) {

	int ax = R[a] + 1, ay = C[a] + 1;
	int bx = R[b] + 1, by = C[b] + 1;

	for (int i = -1; i < 1; i++) {
		for (int j = -1; j < 1; j++) {
			int adja[4] = {RC[ax + i][ay + j], RC[ax + i][ay + j + 1], RC[ax + i + 1][ay + j], RC[ax + i + 1][ay + j + 1]};
			sort(adja, adja + 4);

			update(adja[0], adja[1], -1);
			update(adja[2], adja[3], -1);

			int adjb[4] = {RC[bx + i][by + j], RC[bx + i][by + j + 1], RC[bx + i + 1][by + j], RC[bx + i + 1][by + j + 1]};
			sort(adjb, adjb + 4);

			update(adjb[0], adjb[1], -1);
			update(adjb[2], adjb[3], -1);
		}
	}

	swap(RC[ax][ay], RC[bx][by]);
	swap(R[a], R[b]);
	swap(C[a], C[b]);

	for (int i = -1; i < 1; i++) {
		for (int j = -1; j < 1; j++) {
			int adja[4] = {RC[ax + i][ay + j], RC[ax + i][ay + j + 1], RC[ax + i + 1][ay + j], RC[ax + i + 1][ay + j + 1]};
			sort(adja, adja + 4);

			update(adja[0], adja[1], +1);
			update(adja[2], adja[3], +1);

			int adjb[4] = {RC[bx + i][by + j], RC[bx + i][by + j + 1], RC[bx + i + 1][by + j], RC[bx + i + 1][by + j + 1]};
			sort(adjb, adjb + 4);

			update(adjb[0], adjb[1], +1);
			update(adjb[2], adjb[3], +1);
		}
	}

	return tree[1].ans;
}

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