Submission #75005

#	Time	Username	Problem	Language	Result	Execution time	Memory
75005		ainta	Seats (IOI18_seats)	C++17	100 / 100	2594 ms	103740 KiB

seats

#include "seats.h"
#include <algorithm>
#include <vector>
#define N_ 1010000
#define SZ 1048576
#define pii pair<int,int>
using namespace std;
vector<vector<int> >w;
int H, W, n, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

struct point {
	int x, y;
}P[N_];

int Get(int x, int y) {
	if (x < 0 || x >= H || y < 0 || y >= W)return n;
	return w[x][y];
}

struct Seg {
	int Mn[SZ + SZ];
	int C[SZ + SZ];
	int K[SZ + SZ];
	void UDT(int nd) {
		int mm = min(Mn[nd * 2], Mn[nd * 2 + 1]);
		Mn[nd] = mm;
		C[nd] = 0;
		if (mm == Mn[nd * 2])C[nd] += C[nd * 2];
		if (mm == Mn[nd * 2 + 1])C[nd] += C[nd * 2 + 1];
	}
	void init(int nd, int b, int e) {
		if (b == e) {
			C[nd] = 1;
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void Add2(int nd, int x) {
		Mn[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void Add(int nd, int b, int e, int s, int l, int x) {
		if (b == s && e == l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
		UDT(nd);
	}
}T;

void Put(int x, int y, int ck) {
	int i, j;
	if (x < 0 || x >= H || y < 0 || y >= W)return;
	int t = min(Get(x - 1, y), Get(x, y - 1));
	if (w[x][y] < t)T.Add(1, 0, n - 1, w[x][y], t - 1, ck);
	int TP[4];
	for (i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		TP[i] = Get(tx, ty);
	}
	sort(TP, TP + 4);
	if (TP[1] < w[x][y]) T.Add(1, 0, n - 1, TP[1], w[x][y] - 1, ck);
}

void give_initial_chart(int HH, int WW, std::vector<int> R, std::vector<int> C) {
	int i, j;
	H = HH;
	W = WW;
	n = H*W;
	w.resize(H);
	T.init(1, 0, n - 1);
	for (i = 0; i < H; i++)w[i].resize(W);
	for (i = 0; i < n; i++) {
		P[i] = { R[i],C[i] };
		w[R[i]][C[i]] = i;
	}
	for (i = 0; i < H; i++)for (j = 0; j < W; j++) {
		Put(i, j, 1);
	}
}

int swap_seats(int a, int b) {
	vector<pii>TP;
	TP.push_back({ P[a].x,P[a].y });
	TP.push_back({ P[b].x,P[b].y });
	for (int i = 0; i < 4; i++) {
		TP.push_back({ P[a].x + dx[i], P[a].y + dy[i] });
		TP.push_back({ P[b].x + dx[i], P[b].y + dy[i] });
	}
	sort(TP.begin(), TP.end());
	TP.resize(unique(TP.begin(), TP.end()) - TP.begin());
	for (auto &t : TP) {
		Put(t.first, t.second, -1);
	}
	swap(w[P[a].x][P[a].y], w[P[b].x][P[b].y]);
	swap(P[a], P[b]);
	for (auto &t : TP) {
		Put(t.first, t.second, 1);
	}
	return T.C[1];
}

Compilation message (stderr)

seats.cpp: In function 'void Put(int, int, int)':
seats.cpp:64:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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