Submission #1065126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065126		MinaRagy06	Seats (IOI18_seats)	C++17	100 / 100	3623 ms	167324 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
#define md ((l + r) >> 1)

const int N = 1'000'005, inf = 1e9;
struct node {
	array<int, 2> mn;
	array<int, 2> lazy;
	int cnt;
	node() {
		mn = {0, 0};
		lazy = {0, 0};
		cnt = 0;
	}
	node(array<int, 2> v) {
		mn = v;
		lazy = {0, 0};
		cnt = 1;
	}
	friend node operator+(const node &l, const node &r) {
		node ret = l;
		if (r.mn < ret.mn) {
			ret = r;
		} else if (r.mn == l.mn) {
			ret.cnt += r.cnt;
		}
		return ret;
	}
} seg[1 << 21];

void build(int i, int l, int r) {
	if (l == r) {
		seg[i] = (array<int, 2>) {0, 0};
		return;
	}
	build(i << 1, l, md);
	build(i << 1 | 1, md + 1, r);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void process(int i, int l, int r) {
	if (l != r) {
		for (auto c : {i << 1, i << 1 | 1}) {
			seg[c].lazy[0] += seg[i].lazy[0];
			seg[c].lazy[1] += seg[i].lazy[1];
		}
	}
	seg[i].mn[0] += seg[i].lazy[0];
	seg[i].mn[1] += seg[i].lazy[1];
	seg[i].lazy = {0, 0};
//	cout << "> " << i << ' ' << seg[i].mn[0] << ' ' << seg[i].mn[1] << '\n';
}
void upd(int i, int l, int r, int s, int e, array<int, 2> v) {
	process(i, l, r);
	if (s <= l && r <= e) {
//		cout << v[0] << ' ' << v[1] << '\n';
		seg[i].lazy[0] += v[0];
		seg[i].lazy[1] += v[1];
		process(i, l, r);
		return;
	}
	if (r < s || e < l) {
		return;
	}
	upd(i << 1, l, md, s, e, v);
	upd(i << 1 | 1, md + 1, r, s, e, v);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
int n, m;
vector<int> r, c;
vector<vector<int>> t;
int get(int i, int j) {
	if (i < 0 || i == n || j < 0 || j == m) {
		return n * m;
	}
	return t[i][j];
}
void process(vector<array<int, 2>> pos, int coeff) {
	for (auto [x, y] : pos) {
		vector<int> v;
		for (int i = x; i <= x + 1; i++) {
			for (int j = y; j <= y + 1; j++) {
				v.push_back(get(i, j));
			}
		}
		sort(v.begin(), v.end());
//		cout << v[0] << ' ' << v[1] << ' ' << v[2] << ' ' << v[3] << '\n';
		upd(1, 0, n * m - 1, v[0], v[1] - 1, {coeff, 0});
		upd(1, 0, n * m - 1, v[2], v[3] - 1, {0, coeff});
	}
}
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
	n = _n, m = _m;
	r = _r, c = _c;
	t.resize(n);
	for (int i = 0; i < n; i++) {
		t[i].resize(m);
	}
	for (int i = 0; i < n * m; i++) {
		t[r[i]][c[i]] = i;
	}
	vector<array<int, 2>> v;
	for (int i = -1; i < n; i++) {
		for (int j = -1; j < m; j++) {
			v.push_back({i, j});
		}
	}
	build(1, 0, n * m - 1);
	process(v, 1);
}

int di[4] = {-1, 0, -1, 0};
int dj[4] = {0, -1, -1, 0};
int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	vector<array<int, 2>> v;
	for (auto p : {x, y}) {
		for (int k = 0; k < 4; k++) {
			int i = r[p] + di[k], j = c[p] + dj[k];
			v.push_back({i, j});
		}
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	process(v, -1);
	swap(r[x], r[y]);
	swap(c[x], c[y]);
	t[r[x]][c[x]] = x;
	t[r[y]][c[y]] = y;
	process(v, 1);
	node val = seg[1];
//	cout << val.mn[0] << ' ' << val.mn[1] << '\n';
	return val.cnt;
}

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