Submission #1073139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073139		Tob	Seats (IOI18_seats)	C++14	100 / 100	1281 ms	77908 KiB

seats

#include <bits/stdc++.h>
 
#include "seats.h"
 
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
typedef array <int, 3> node;
 
const int ofs = (1 << 20);
int n, m;
int r[ofs], c[ofs], mat[3*ofs], dx[4];
node t[2*ofs];
 
node Merge(node x, node y) {
	y[1] += x[0];
	if (x[1] < y[1]) {x[0] += y[0]; return x;}
	if (x[1] > y[1]) {y[0] += x[0]; return y;}
	return {x[0]+y[0], x[1], x[2]+y[2]};
}
 
void add(int x, int val) {
	if (x == ofs) return;
	x += ofs;
	t[x][0] += val;
	t[x][1] += val;
	t[x][2] = 1;
	while (x /= 2) t[x] = Merge(t[2*x], t[2*x+1]);
}
 
int get() {return t[1][2];}
 
void give_initial_chart(int n_, int m_, vector<int> r_, vector<int> c_) {
	n = n_; m = m_;
	dx[0] = 1; dx[1] = m+2; dx[2] = -1; dx[3] = -m-2;
	for (int i = 0; i < n*m; i++) r[i] = r_[i]+1, c[i] = c_[i]+1;
	for (int i = 0; i <= n+1; i++) mat[i*(m+2)] = mat[i*(m+2)+m+1] = ofs;
	for (int i = 0; i <= m+1; i++) mat[i] = mat[(n+1)*(m+2)+i] = ofs;
	for (int i = 0; i < n*m; i++) mat[r[i]*(m+2)+c[i]] = i;
	for (int i = 1; i <= n+1; i++) {
		for (int j = 1; j <= m+1; j++) {
			int x = i*(m+2)+j;
			int b[4] = {mat[x-m-3], mat[x-m-2], mat[x-1], mat[x]};
			sort(b, b+4);
			add(b[0], 1);
			add(b[1], -1);
			add(b[2], 1);
			add(b[3], -1);
		}
	}
}
 
void upd(int x, int o) {
	for (int i = 0; i < 4; i++) {
		int b[4] = {mat[x], mat[x+dx[i]], mat[x+dx[(i+1)&3]], mat[x+dx[i]+dx[(i+1)&3]]};
		sort(b, b+4);
		add(b[0], o);
		add(b[1], -o);
		add(b[2], o);
		add(b[3], -o);
	}
}
 
int swap_seats(int a, int b) {
	int pa = r[a]*(m+2)+c[a], pb = r[b]*(m+2)+c[b];
	upd(pa, -1);
	upd(pb, -1);
	swap(mat[pa], mat[pb]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	upd(pa, 1);
	upd(pb, 1);
	return get();
}

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