Submission #78692

#	Time	Username	Problem	Language	Result	Execution time	Memory
78692		tincamatei	Seats (IOI18_seats)	C++14	31 / 100	3629 ms	262380 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

template<int n, typename T, typename Updater>
class LazyAint {
private:
	T neutralUpd, neutralQry, initval;
	T *aint;
	T *lazy;
	Updater upd;
	int lInit, rInit;

	void pushlazy(int nod, int l, int r) {
		aint[nod] = upd.update(aint[nod], lazy[nod], r - l + 1);
		
		if(2 * nod <= 4 * n)
			lazy[2 * nod] = upd.update(lazy[2 * nod], lazy[nod], r - l + 1);
		if(2 * nod + 1 <= 4 * n)
			lazy[2 * nod + 1] = upd.update(lazy[2 * nod + 1], lazy[nod], r - l + 1);
		lazy[nod] = neutralUpd;
	}
	void updateDfs(int i, int j, T val, int nod = 1, int l = 1, int r = n) {
		pushlazy(nod, l, r);
		if(r < i || j < l || r < l || j < i)
			return ;
		if(i <= l && r <= j) {
			lazy[nod] = upd.update(lazy[nod], val, r - l + 1);
			pushlazy(nod, l, r);
			return;
		}
		int mid = (l + r) / 2;
		if(l < r) {
			updateDfs(i, j, val, 2 * nod, l, mid);
			updateDfs(i, j, val, 2 * nod + 1, mid + 1, r);
			aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
		}
	}
	T queryDfs(int i, int j, int nod = 1, int l = 1, int r = n) {
		if(r < i || j < l || r < l || j < i)
			return neutralQry;
		pushlazy(nod, l, r);
		if(i <= l && r <= j)
			return aint[nod];
		int mid = (l + r) / 2;
		return upd.query(queryDfs(i, j, 2 * nod, l, mid),
		                 queryDfs(i, j, 2 * nod + 1, mid + 1, r));
	}
	void initDfs(int nod, int l, int r) {
		int mid = (l + r) / 2;
		if(l < r) {
			initDfs(2 * nod, l, mid);
			initDfs(2 * nod + 1, mid + 1, r);
			aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
		} else
			aint[nod] = initval;
	}
public:
	LazyAint(T _neutralUpd, T _neutralQry, T _initval, int _lInit = 1, int _rInit = n) {
		neutralUpd = _neutralUpd;
		neutralQry = _neutralQry;
		initval = _initval;
		
		lInit = _lInit;
		rInit = _rInit;

		aint = new T[1 + 4 * n];
		lazy = new T[1 + 4 * n];
		
		for(int i = 0; i <= 4 * n; ++i)
			lazy[i] = neutralUpd;
		initDfs(1, lInit, rInit);
	}
	void update(int i, int j, T val) {
		updateDfs(i, j, val, 1, lInit, rInit);
	}
	T query(int i, int j) {
		return queryDfs(i, j, 1, lInit, rInit);
	}
};

const int MAX_N = 1000000;

struct Node {
	int minVal, fr;
	
	Node update(Node a, Node b, int x) {
		a.minVal += b.minVal;
		return a;
	}
	Node query(Node a, Node b) {
		if(b.minVal < a.minVal) {
			a.minVal = b.minVal;
			a.fr = b.fr;
		} else if(b.minVal == a.minVal)
			a.fr += b.fr;
		return a;
	}
};

LazyAint<1+MAX_N, Node, Node> aint({0, 0}, {MAX_N + 1, 0}, {0, 1}, 0, MAX_N);

int N;
int cells[4];
int **matr;

vector<int> R, C;

void activateSqr(int l, int c, int x) {
	cells[0] = matr[l][c];
	cells[1] = matr[l + 1][c];
	cells[2] = matr[l][c + 1];
	cells[3] = matr[l + 1][c + 1];
	std::sort(cells, cells + 4);
	aint.update(cells[0], cells[1] - 1, {x, 0});
	aint.update(cells[2], cells[3] - 1, {4 * x, 0});
}

void activateCells(int l, int c, int x) {
	activateSqr(l, c, x);
	activateSqr(l - 1, c, x);
	activateSqr(l, c - 1, x);
	activateSqr(l - 1, c - 1, x);
}

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
	N = H * W;
	R = _R;
	C = _C;
	matr = new int*[1 + H + 1];
	for(int i = 0; i <= H + 1; ++i) {
		matr[i] = new int[1 + W + 1];
		for(int j = 0; j <= W + 1; ++j)
			matr[i][j] = N;
	}

	for(int i = 0; i < N; ++i) {
		R[i]++;
		C[i]++;
		matr[R[i]][C[i]] = i;
	}
	for(int i = 0; i <= H; ++i)
		for(int j = 0; j <= W; ++j)
			activateSqr(i, j, 1);
}

int swap_seats(int a, int b) {
	activateCells(R[a], C[a], -1);
	activateCells(R[b], C[b], -1);
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	swap(matr[R[a]][C[a]], matr[R[b]][C[b]]);
	activateCells(R[a], C[a], 1);
	activateCells(R[b], C[b], 1);
	
	Node x = aint.query(0, N - 1);
	if(x.minVal != 4)
		return 0;
	return x.fr;
}

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