Submission #630379

#	Time	Username	Problem	Language	Result	Execution time	Memory
630379		abeker	Seats (IOI18_seats)	C++17	100 / 100	2844 ms	228784 KiB

seats

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

typedef pair <int, int> pii;

const int MAXN = 1e6 + 5;
const int offset = 1 << 20;
const int INF = 1e9;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct node {
	int mini, occ, lazy;
};
	
struct tournament {
	node t[2 * offset];
	
	node merge(node l, node r) {
		node res;
		res.mini = min(l.mini, r.mini);
		res.occ = 0;
		if (l.mini == res.mini)
			res.occ += l.occ;
		if (r.mini == res.mini)
			res.occ += r.occ;
		res.lazy = l.lazy + r.lazy;
		return res;
	}
	
	void init(int n) {
		for (int i = 0; i < offset; i++)	
			t[i + offset] = {i < n ? -1 : INF, 1, 0};
		for (int i = offset - 1; i >= 0; i--)
			t[i] = merge(t[2 * i], t[2 * i + 1]);
	}
	
	void prop(int x) {
		t[x].mini += t[x].lazy;
		if (x < offset) {
			t[2 * x].lazy += t[x].lazy;
			t[2 * x + 1].lazy += t[x].lazy;
		}
		t[x].lazy = 0;
	}
	
	void update(int x, int lo, int hi, int from, int to, int val) {
		prop(x);
		if (lo >= to || hi <= from)
			return;
		if (lo >= from && hi <= to) {
			t[x].mini += val;
			if (x < offset) {
				t[2 * x].lazy += val;
				t[2 * x + 1].lazy += val;
			}
			return;
		}
		int mid = (lo + hi) / 2;
		update(2 * x, lo, mid, from, to, val);
		update(2 * x + 1, mid, hi, from, to, val);
		t[x] = merge(t[2 * x], t[2 * x + 1]);
	}
	
	node query(int x, int lo, int hi, int from, int to) {
		prop(x);
		if (lo >= to || hi <= from)
			return {INF, 1, 0};
		if (lo >= from && hi <= to)
			return t[x];
		int mid = (lo + hi) / 2;
		return merge(query(2 * x, lo, mid, from, to), query(2 * x + 1, mid, hi, from, to));
	}
	
	void update(int from, int to) {
		if (from < to)
			update(1, 0, offset, from, to, 1);
		else
			update(1, 0, offset, to, from, -1);
	}
	
	int query(int from, int to) {
		node tmp = query(1, 0, offset, from, to);
		return tmp.mini ? 0 : tmp.occ;
	}
};

int N, H, W;
vector <int> r, c;
vector < vector <int> > mat, mn1, mn2;
tournament T;

bool ok(int x, int y) {
	return x > 0 && y > 0 && x <= H && y <= W;
}

void change(int x, int y) {
	int old = mn1[x][y];
	mn1[x][y] = max(min(mat[x - 1][y], mat[x][y - 1]), mat[x][y]);
	T.update(old, mn1[x][y]);
	
	vector <int> adj;
	for (int i = 0; i < 4; i++)
		adj.push_back(mat[x + dx[i]][y + dy[i]]);
	
	sort(adj.begin(), adj.end());
	
	old = mn2[x][y];
	mn2[x][y] = min(adj[1], mat[x][y]);
	T.update(mn2[x][y], old);
}

void update_all(int x, int y) {
	change(x, y);
	for (int i = 0; i < 4; i++)
		if (ok(x + dx[i], y + dy[i]))
			change(x + dx[i], y + dy[i]);
}

void give_initial_chart(int h, int w, vector <int> R, vector <int> C) {
	H = h;
	W = w;
	r = R;
	c = C;
	N = H * W;
	T.init(N);
	
	mat.resize(H + 2);
	mn1.resize(H + 2);
	mn2.resize(H + 2);
	for (int i = 0; i < H + 2; i++) 
		mat[i] = mn1[i] = mn2[i] = vector <int> (W + 2, N);
	
	for (int i = 0; i < N; i++) {
		r[i]++; c[i]++;
		mat[r[i]][c[i]] = mn1[r[i]][c[i]] = mn2[r[i]][c[i]] = i;
	}
	
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			change(i, j);	
}

int swap_seats(int a, int b) {
	swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	
	update_all(r[a], c[a]);
	update_all(r[b], c[b]);
  
  return T.query(0, N);
}

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