Submission #78695

#	Time	Username	Problem	Language	Result	Execution time	Memory
78695		tincamatei	Seats (IOI18_seats)	C++14	0 / 100	2970 ms	48500 KiB

seats

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

using namespace std;

const int MAX_N = 1000000;

int val[1+4*MAX_N], fr[1+4*MAX_N];
int lazy[1+4*MAX_N];

static inline void pushLazy(int nod, int l, int r) {
	val[nod] -= lazy[nod];
	if(l < r) {
		lazy[2 * nod] += lazy[nod];
		lazy[2 * nod + 1] += lazy[nod];
	}
	lazy[nod] = 0;
}

void init(int l, int r, int nod = 1) {
	if(l == r)
		val[nod] = 0, fr[nod] = 1;
	else {
		int mid = (l + r) / 2;
		init(l, mid, 2 * nod);
		init(mid + 1, r, 2 * nod);
		if(val[2 * nod] < val[2 * nod + 1])
			val[nod] = val[2 * nod], fr[nod] = fr[2 * nod];
		else if(val[2 * nod + 1] < val[2 * nod])
			val[nod] = val[2 * nod + 1], fr[nod] = fr[2 * nod + 1];
		else
			val[nod] = val[2 * nod], fr[nod] = fr[2 * nod] + fr[2 * nod + 1];
	}
}

void update(int i, int j, int valU, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(r < i || j < l || j < i || r < l)
		return;
	
	int mid = (l + r) / 2;
	if(i <= l && r <= j) {
		lazy[nod] += valU;
		pushLazy(nod, l, r);
	} else {
		update(i, j, valU, l, mid, 2 * nod);
		update(i, j, valU, mid + 1, r, 2 * nod + 1);
		val[nod] = val[2 * nod], fr[nod] = fr[2 * nod];
		if(val[2 * nod + 1] < val[nod])
			val[nod] = val[2 * nod + 1], fr[nod] = fr[2 * nod + 1];
		else if(val[nod] == val[2 * nod + 1])
			fr[nod] += fr[2 * nod + 1];
	}
}

pair<int, int> query(int i, int j, int l, int r, int nod = 1) {
	pushLazy(nod, l, r);
	if(j < i || r < i || j < l || r < l)
		return make_pair(MAX_N + 1, 0);
	
	int mid = (l + r) / 2;
	if(i <= l && r <= j)
		return make_pair(val[nod], fr[nod]);
	else {
		pair<int, int> r1 = query(i, j, l, mid, 2 * nod),
		               r2 = query(i, j, mid + 1, r, 2 * nod + 1);
		if(r2.first < r1.first)
			r1 = r2;
		else if(r2.first == r1.first)
			r1.second += r2.second;
		return r1;
	}
}

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

vector<int> R, C;

static inline 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);
	update(cells[0], cells[1] - 1, x, 0, N);
	update(cells[2], cells[3] - 1, 4 * x, 0, N);
}

static inline 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;
	
	init(0, N, 1);

	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);
	
	pair<int, int> x = query(0, N - 1, 0, N);
	if(x.first != 4)
		return 0;
	return x.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