제출 #293816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293816		Mlxa	Furniture (JOI20_furniture)	C++14	0 / 100	65 ms	63008 KiB

furniture

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define all(x) x.begin(), x.end()

const int S = 1000;
const int N = 1 << 20;
const int H = 5e7;

int val[H];
int *ptr[H];
int saved = 0;

void save(int &x) {
	assert(saved < H);
	val[saved] = x;
	ptr[saved] = &x;
	++saved;
}
void rollback(int savepoint) {
	while (saved > savepoint) {
		--saved;
		*ptr[saved] = val[saved];
	}
}
int n, m, q;
bool ok(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < m;
}
int id(int i, int j) {
	return S * i + j;
}
int dx[] = {-1, 0, +1, 0};
int dy[] = {0, -1, 0, +1};
vector<int> nei(int v) {
	int i = v / S, j = v % S;
	vector<int> ans;
	for (int d = 0; d < 4; ++d) {
		int x = i + dx[d], y = j + dy[d];
		if (ok(x, y)) {
			ans.push_back(id(x, y));
		}
	}
	return ans;
}
int state[N];
int par[N];
int siz[N];
int dsu(int v) {
	while (par[v] != v) {
		v = par[v];
	}
	return v;
}
void merge(int x, int y) {
	x = dsu(x);
	y = dsu(y);
	if (x == y) {
		return;
	}
	if (siz[x] > siz[y]) {
		swap(x, y);
	}
	save(par[x]);
	save(siz[y]);
	par[x] = y;
	siz[y] += siz[x];
}
void on(int v) {
	save(state[v]);
	state[v] = 1;
	for (int u : nei(v)) {
		if (state[u]) {
			merge(v, u);
		}
	}
}
bool is_connected() {
	return dsu(id(0, 0)) == dsu(id(n - 1, m - 1));
}
vector<int> tree[2 * N];
void add_vertex(int l, int r, int v) {
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			tree[l++].push_back(v);
		}
		if (r % 2 == 0) {
			tree[r--].push_back(v);
		}
	}
}
int query[N];
int first[N];
int answer[N];
void umin(int &a, int b) {
	a = min(a, b);
}
void solve(int v) {
	int savepoint = saved;
	for (int u : tree[v]) {
		on(u);
	}
	if (v >= N) {
		if (!(answer[v - N] = is_connected())) {
			int u = query[v - N];
			add_vertex(v - N + 1, N - 1, u);
		}
	} else {
		solve(v + v);
		solve(v + v + 1);
	}
	rollback(savepoint);
}
signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	iota(par, par + N, 0);
	fill_n(siz, N, 1);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c;
			cin >> c;
			int v = id(i, j);
			if (c == '0') {
				first[v] = N;
			} else {
				first[v] = -1;
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int x, y;
		cin >> x >> y;
		query[i] = id(x - 1, y - 1);
		assert(first[query[i]] > i);
		first[query[i]] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int v = id(i, j);
			//cerr << first[v] << " ";
			add_vertex(0, first[v] - 1, v);
		}
		//cerr << endl;
	}
	solve(1);
	for (int i = 0; i < q; ++i) {
		cout << answer[i] << "\n";
	}
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95