Submission #1055170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055170		MinaRagy06	Seats (IOI18_seats)	C++17	25 / 100	4086 ms	81524 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;
struct node {
	int mn, mx;
	node() {
		mn = 1e9;
		mx = -1e9;
	}
	friend node operator+(const node &l, const node &r) {
		node ret;
		ret.mn = min(l.mn, r.mn);
		ret.mx = max(l.mx, r.mx);
		return ret;
	}
};
struct segtree {
	node seg[1 << 21];
	vector<int> a;
	void build(int i, int l, int r) {
		if (l == r) {
			seg[i].mn = seg[i].mx = a[l];
			return;
		}
		build(i << 1, l, md);
		build(i << 1 | 1, md + 1, r);
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
	node get(int i, int l, int r, int s, int e) {
		if (s <= l && r <= e) {
			return seg[i];
		}
		if (r < s || e < l) {
			return node();
		}
		return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
	}
	void upd(int i, int l, int r, int x, int v) {
		if (l == r) {
			seg[i].mn = seg[i].mx = v;
			return;
		}
		if (x <= md) {
			upd(i << 1, l, md, x, v);
		} else {
			upd(i << 1 | 1, md + 1, r, x, v);
		}
		seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}
} segr, segc;
int n, m;
vector<int> r, c;
void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
	n = _n, m = _m;
	r = _r, c = _c;
	segr.a = r;
	segc.a = c;
	segr.build(1, 0, n * m - 1);
	segc.build(1, 0, n * m - 1);
}

int swap_seats(int x, int y) {
	if (x > y) swap(x, y);
	swap(r[x], r[y]);
	segr.upd(1, 0, n * m - 1, x, r[x]);
	segr.upd(1, 0, n * m - 1, y, r[y]);
	swap(c[x], c[y]);
	segc.upd(1, 0, n * m - 1, x, c[x]);
	segc.upd(1, 0, n * m - 1, y, c[y]);

	int i = 0, cnt = 0;
	while (i < n * m) {
		node vr = segr.get(1, 0, n * m - 1, 0, i);
		node vc = segc.get(1, 0, n * m - 1, 0, i);
		int val = (vr.mx - vr.mn + 1) * (vc.mx - vc.mn + 1);
		if (val == i + 1) {
			cnt++;
			i++;
		} else {
			i = val - 1;
		}
	}
	return cnt;
}

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