Submission #70351506

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
template <typename T> bool chmin(T &x, T y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
using SS = array<int, 3>;
using S = array<SS, 3>;
array<S, 9> e8;
S op(S x, S y) {
	if (x[0][0] == -1)
		return y;
	if (y[0][0] == -1)
		return x;
	S res = e8[7];
	rep(i, 3) rep(j, 3) rep(k, 3) chmin(res[i][j], x[k][j] + y[i][k]);
	return res;
}
S e() { return e8[8]; }
constexpr int INF = 1e9;
int main() {
	e8[0] = S{SS{0, 1, 2}, SS{1, 0, 1}, SS{2, 1, 0}};
	e8[1] = S{SS{INF, INF, INF}, SS{INF, 0, 1}, SS{INF, 1, 0}};
	e8[2] = S{SS{0, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, 0}};
	e8[3] = S{SS{INF, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, 0}};
	e8[4] = S{SS{0, 1, INF}, SS{1, 0, INF}, SS{INF, INF, INF}};
	e8[5] = S{SS{INF, INF, INF}, SS{INF, 0, INF}, SS{INF, INF, INF}};
	e8[6] = S{SS{0, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, INF}};
	e8[7] = S{SS{INF, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, INF}};
	e8[8] = S{SS{-1, -1, -1}, SS{-1, -1, -1}, SS{-1, -1, -1}};
	int n;
	cin >> n;
	vector<int> s(n);
	rep(j, 3) {
		string ss;
		cin >> ss;
		rep(i, n) if (ss[i] == '#') s[i] |= 1 << j;
	}
	vector<S> to_seg(n);
	rep(i, n) to_seg[i] = e8[s[i]];
	atcoder::segtree<S, op, e> seg(to_seg);
	int que;
	cin >> que;
	while (que--) {
		int r, c;
		cin >> r >> c;
		r--, c--;
		s[c] ^= 1 << r;
		seg.set(c, e8[s[c]]);
		auto res = seg.all_prod();
		cout << (res[2][0] == INF ? -1 : n - 1 + res[2][0]) << '\n';
	}
}

Submission Info

Judge Result