Submission #1029760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029760		AmirAli_H1	Seats (IOI18_seats)	C++17	100 / 100	2831 ms	144948 KiB

seats

// In the name of Allah

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 20) + 4;
const int oo = 1e9 + 7;

struct node {
	ll lazy, min, num;
};

int n, m, sz;
pii A[maxn]; vector<int> ind[maxn];
node t[2 * maxn]; vector<pii> ls;
vector<pair<int, pii>> vc; int M[2][2];

node f(node a, node b, ll lazy) {
	node res;
	res.min = min(a.min, b.min); res.num = 0;
	if (res.min == a.min) res.num += a.num;
	if (res.min == b.min) res.num += b.num;
	res.lazy = lazy; res.min += lazy;
	return res;
}

void build(int v, int tl, int tr) {
	t[v].lazy = 0;
	if (tr - tl == 1) {
		t[v].min = 0; t[v].num = 1;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v].lazy += x; t[v].min += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void addx(int x, int y, ll R) {
	vc.clear();
	for (int i = x - 1; i <= x; i++) {
		for (int j = y - 1; j <= y; j++) {
			if (i < 0 || i >= n || j < 0 || j >= m) continue;
			vc.pb(Mp(ind[i][j], Mp(i - x + 1, j - y + 1)));
		}
	}
	sort(all(vc));
	
	M[0][0] = M[0][1] = M[1][0] = M[1][1] = 0;
	for (int i = 0; i < len(vc); i++) {
		int l = vc[i].F, r = sz;
		if (i + 1 < len(vc)) r = vc[i + 1].F;
		int i1 = vc[i].S.F, j1 = vc[i].S.S;
		M[i1][j1] = 1; int T = 0;
		T += (M[0][0] != M[0][1] && M[0][0] != M[1][0]);
		T += (M[0][1] != M[0][0] && M[0][1] != M[1][1]);
		T += (M[1][0] != M[1][1] && M[1][0] != M[0][0]);
		T += (M[1][1] != M[1][0] && M[1][1] != M[0][1]);
		add_val(0, 0, sz, l, r, R * T);
	}
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H; m = W; sz = n * m;
	for (int i = 0; i < n; i++) ind[i].resize(m);
	for (int i = 0; i < sz; i++) {
		A[i] = Mp(R[i], C[i]);
		ind[A[i].F][A[i].S] = i;
	}
	
	build(0, 0, sz);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) addx(i, j, 1);
	}
}

int swap_seats(int a, int b) {
	ls.clear();
	for (int i : {a, b}) {
		for (int x : {A[i].F, A[i].F + 1}) {
			for (int y : {A[i].S, A[i].S + 1}) {
				ls.pb(Mp(x, y));
			}
		}
	}
	sort(all(ls)); ls.resize(unique(all(ls)) - ls.begin());
	
	for (auto f : ls) addx(f.F, f.S, -1);
	swap(A[a], A[b]);
	for (int i : {a, b}) ind[A[i].F][A[i].S] = i;
	for (auto f : ls) addx(f.F, f.S, 1);
	return t[0].num;
}

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