Submission #1065092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065092		MinaRagy06	Seats (IOI18_seats)	C++17	33 / 100	409 ms	73568 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 {
	int mn;
	int lazy;
	int cnt;
	node() {
		mn = 0;
		lazy = 0;
		cnt = 0;
	}
	node(int v) {
		mn = v;
		lazy = 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, vector<int> &v) {
	if (l == r) {
		seg[i] = v[l];
		return;
	}
	build(i << 1, l, md, v);
	build(i << 1 | 1, md + 1, r, v);
	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 += seg[i].lazy;
		}
	}
	seg[i].mn += seg[i].lazy;
	seg[i].lazy = 0;
}
void upd(int i, int l, int r, int s, int e, int v) {
	process(i, l, r);
	if (s <= l && r <= e) {
		seg[i].lazy += v;
		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;
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;
	}
	int comps = 0;
	vector<int> v(n * m);
	for (int i = 0; i < n * m; i++) {
		int p = c[i];
		if (p - 1 >= 0 && p + 1 < m) {
			comps -= t[0][p - 1] < i && t[0][p + 1] < i;
		}
		comps += (p == 0 || t[0][p - 1] > i) && (p + 1 == m || t[0][p + 1] > i);
		v[i] = comps;
	}
	build(1, 0, n * m - 1, v);
}

void process(vector<int> pos, int coeff) {
	sort(pos.begin(), pos.end());
	pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
	for (auto p : pos) {
		if (p == -1 || p == m) continue;
		int v = 0;
		if (p - 1 >= 0 && p + 1 < m) {
			v -= t[0][p - 1] < t[0][p] && t[0][p + 1] < t[0][p];
		}
		v += (p == 0 || t[0][p - 1] > t[0][p]) && (p + 1 == m || t[0][p + 1] > t[0][p]);
		v *= coeff;
		upd(1, 0, n * m - 1, t[0][p], n * m - 1, v);
	}
}
int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	vector<int> v = {c[x] - 1, c[x], c[x] + 1, c[y] - 1, c[y], c[y] + 1};
	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];
	return val.cnt;
}

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