Submission #1035485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035485		lovrot	Seats (IOI18_seats)	C++17	100 / 100	2067 ms	118696 KiB

seats

#include "seats.h"
#include <cassert>
#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair<int, int> pii;

const int LOG = 20;
const int N = 1 << LOG;
const int OO = 2e9;

int n, m, X[N], Y[N];
vector<vector<int>> mat;

int t[2 * N], c[2 * N], p[2 * N];

void propagate(int u) { 
	t[2 * u] += p[u];
	t[2 * u + 1] += p[u];
	p[2 * u] += p[u];
	p[2 * u + 1] += p[u];
	p[u] = 0;
}

pii merge(pii a, pii b) { 
	pii c;
	c.X = min(a.X, b.X);
	c.Y = (a.X == c.X ? a.Y : 0) + (b.X == c.X ? b.Y : 0);
	return c;
}

void update(int l, int r, int w, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return; }
	if(l <= lo && hi <= r) { 
		t[u] += w;
		p[u] += w;
		return;
	}
	int mi = (lo + hi) / 2;
	propagate(u);
	update(l, r, w, 2 * u, lo, mi);
	update(l, r, w, 2 * u + 1, mi, hi);
	pii res = merge({t[2 * u], c[2 * u]}, {t[2 * u + 1], c[2 * u + 1]});
	t[u] = res.X;
	c[u] = res.Y;
}

pii query(int l, int r, int u = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return {OO, 0}; }
	if(l <= lo && hi <= r) { 
		return {t[u], c[u]};
	}
	int mi = (lo + hi) / 2;
	propagate(u);
	return merge(query(l, r, 2 * u, lo, mi), query(l, r, 2 * u + 1, mi, hi));
}

void add(int x, int y, int w) {
	vector<int> v;
	for(int i = 0; i < 2; ++i) { 
		for(int j = 0; j < 2; ++j) { 
			v.PB(mat[x + i][y + j]);
		}
	}

	sort(v.begin(), v.end());

	update(v[0], v[1], w);
	update(v[2], v[3], 10 * w);
}

void give_initial_chart(int nn, int mm, vector<int> XX, vector<int> YY) {
	for(int i = 2 * N - 1; i > 0; --i) {
		c[i] = 1;
		if(i < N) { c[i] = c[2 * i] + c[2 * i + 1]; }
	}

	n = nn;
	m = mm; 
	mat.resize(n + 2);
	for(int i = 0; i <= n + 1; ++i) { 
		mat[i].resize(m + 2, n * m + 1);
	}

	for(int i = 1; i <= n * m; ++i) {
		X[i] = XX[i - 1] + 1;
		Y[i] = YY[i - 1] + 1; 

		mat[X[i]][Y[i]] = i;
	}
	
	for(int i = 0; i <= n; ++i) { 
		for(int j = 0; j <= m; ++j) { 
			add(i, j, 1);
		}
	}
}

int swap_seats(int a, int b) {
	++a; ++b;
	for(int i = 0; i < 2; ++i) { 
		for(int j = 0; j < 2; ++j) { 
			add(X[a] - i, Y[a] - j, -1);
			add(X[b] - i, Y[b] - j, -1);
		}
	}

	swap(mat[X[a]][Y[a]], mat[X[b]][Y[b]]);
	swap(X[a], X[b]);
	swap(Y[a], Y[b]);

	for(int i = 0; i < 2; ++i) { 
		for(int j = 0; j < 2; ++j) { 
			add(X[a] - i, Y[a] - j, 1);
			add(X[b] - i, Y[b] - j, 1);
		}
	}

	return query(1, n * m + 1).Y;
}

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