Submission #435757

#	Time	Username	Problem	Language	Result	Execution time	Memory
435757		rainboy	Seats (IOI18_seats)	C++11	100 / 100	2256 ms	108160 KiB

seats

#include "seats.h"
#include <stdlib.h>

using namespace std;

const int N = 1000000, N_ = 1 << 20, INF = 0x3f3f3f3f;	// N_ = pow2(ceil(log2(N)))

typedef vector<int> vi;

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int max(int a, int b) { return a > b ? a : b; }
int max2(int a, int b, int c, int d) {
	if (a < b)
		return max2(b, a, c, d);
	if (a < c)
		return max2(c, b, a, d);
	if (a < d)
		return max2(d, b, c, a);
	return max(max(b, c), d);
}

long long sum[N_ * 2], pref[N_ * 2]; int kk[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;
	long long x, y;

	sum[i] = sum[l] + sum[r];
	x = pref[l], y = sum[l] + pref[r];
	if (x < y)
		pref[i] = x, kk[i] = kk[l];
	else if (x > y)
		pref[i] = y, kk[i] = kk[r];
	else
		pref[i] = x, kk[i] = kk[l] + kk[r];
}

void update(int i, long long x) {
	i += n_;
	pref[i] = sum[i] += x;
	while (i > 1)
		pul(i >>= 1);
}

int **aa, ii[N], jj[N], n, m;

void give_initial_chart(int n1, int m_, vi ii_, vi jj_) {
	int i, j, a;

	n = n1, m = m_;
	aa = (int **) malloc(n * sizeof *aa);
	for (i = 0; i < n; i++)
		aa[i] = (int *) malloc(m * sizeof *aa[i]);
	for (a = 0; a < n * m; a++) {
		ii[a] = ii_[a], jj[a] = jj_[a];
		aa[ii[a]][jj[a]] = a;
	}
	n_ = 1;
	while (n_ < n * m)
		n_ <<= 1;
	for (i = 0; i < n * m; i++)
		sum[n_ + i] = pref[n_ + i] = 1, kk[n_ + i] = 1;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			if (i > 0)
				update(max(aa[i - 1][j], aa[i][j]), -1);
			if (j > 0)
				update(max(aa[i][j - 1], aa[i][j]), -1);
			if (i > 0 && j > 0) {
				int a = aa[i - 1][j - 1], b = aa[i - 1][j], c = aa[i][j - 1], d = aa[i][j];

				update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
			}
		}
}

int swap_seats(int a, int b) {
	int h, i, j, i1 = ii[a], j1 = jj[a], i2 = ii[b], j2 = jj[b];

	for (h = 0; h < 4; h++) {
		i = i1 + di[h], j = j1 + dj[h];
		if (i >= 0 && i < n && j >= 0 && j < m)
			update(max(aa[i1][j1], aa[i][j]), 1);
		i = i2 + di[h], j = j2 + dj[h];
		if (i >= 0 && i < n && j >= 0 && j < m && (i != i1 || j != j1))
			update(max(aa[i2][j2], aa[i][j]), 1);
	}
	for (i = max(i1 - 1, 0); i <= i1 && i + 1 < n; i++)
		for (j = max(j1 - 1, 0); j <= j1 && j + 1 < m; j++) {
			int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];

			update(max2(a, b, c, d), -INF), update(max(max(a, b), max(c, d)), INF - 1);
		}
	for (i = max(i2 - 1, 0); i <= i2 && i + 1 < n; i++)
		for (j = max(j2 - 1, 0); j <= j2 && j + 1 < m; j++) {
			int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];

			if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
				update(max2(a, b, c, d), -INF), update(max(max(a, b), max(c, d)), INF - 1);
		}
	aa[i1][j1] = b, aa[i2][j2] = a, ii[a] = i2, jj[a] = j2, ii[b] = i1, jj[b] = j1;
	for (h = 0; h < 4; h++) {
		i = i1 + di[h], j = j1 + dj[h];
		if (i >= 0 && i < n && j >= 0 && j < m)
			update(max(aa[i1][j1], aa[i][j]), -1);
		i = i2 + di[h], j = j2 + dj[h];
		if (i >= 0 && i < n && j >= 0 && j < m && (i != i1 || j != j1))
			update(max(aa[i2][j2], aa[i][j]), -1);
	}
	for (i = max(i1 - 1, 0); i <= i1 && i + 1 < n; i++)
		for (j = max(j1 - 1, 0); j <= j1 && j + 1 < m; j++) {
			int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];

			update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
		}
	for (i = max(i2 - 1, 0); i <= i2 && i + 1 < n; i++)
		for (j = max(j2 - 1, 0); j <= j2 && j + 1 < m; j++) {
			int a = aa[i][j], b = aa[i][j + 1], c = aa[i + 1][j], d = aa[i + 1][j + 1];

			if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
				update(max2(a, b, c, d), INF), update(max(max(a, b), max(c, d)), -INF + 1);
		}
	return kk[1];
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:102:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  102 |    if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
      |        ~~~~~~~~^~~~~~~~~~~~~~
seats.cpp:124:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  124 |    if (i != i1 && i != i1 - 1 || j != j1 && j != j1 - 1)
      |        ~~~~~~~~^~~~~~~~~~~~~~

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