Submission #70454499

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

#define int long long

int n;
bool s[N][3];

struct Vector {
	int a[3];
	
	Vector() { memset(a, 0x3f, sizeof a); }
	Vector(int x, int y, int z) { a[0] = x, a[1] = y, a[2] = z; }
};
struct Matrix {
	int a[3][3];
	
	Matrix() { memset(a, 0x3f, sizeof a); }
	Matrix(int i) {
		a[0][0] = s[i][0] ? 1 : INF;
		a[1][0] = s[i][0] && s[i][1] ? 2 : INF;
		a[2][0] = s[i][0] && s[i][1] && s[i][2] ? 3 : INF;
		
		a[0][1] = s[i][0] && s[i][1] ? 2 : INF;
		a[1][1] = s[i][1] ? 1 : INF;
		a[2][1] = s[i][1] && s[i][2] ? 2 : INF;
		
		a[0][2] = s[i][0] && s[i][1] && s[i][2] ? 3 : INF;
		a[1][2] = s[i][1] && s[i][2] ? 2 : INF;
		a[2][2] = s[i][2] ? 1 : INF;
	}
};

Matrix operator *(Matrix A, Matrix B) {
	Matrix res;
	for (int i = 0; i < 3; ++ i )
		for (int j = 0; j < 3; ++ j )
			for (int k = 0; k < 3; ++ k )
				res.a[i][j] = min(res.a[i][j], A.a[i][k] + B.a[k][j]);
	return res;
}

Vector operator *(Vector A, Matrix B) {
	Vector res;
	for (int i = 0; i < 3; ++ i )
		for (int j = 0; j < 3; ++ j )
			res.a[j] = min(res.a[j], A.a[i] + B.a[i][j]);
	return res;
}

struct Tree {
	struct Node {
		int l, r;
		Matrix v;
	}tr[N << 2];
	
	void pushup(int u) {
		tr[u].v = tr[u << 1].v * tr[u << 1 | 1].v;
	}
	
	void build(int u, int l, int r) {
		tr[u].l = l, tr[u].r = r;
		if (l == r) tr[u].v = Matrix(l);
		else {
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
			pushup(u);
		}
	}
	
	void modify(int u, int x) {
		if (tr[u].l == tr[u].r) tr[u].v = Matrix(x);
		else {
			int mid = tr[u].l + tr[u].r >> 1;
			if (x <= mid) modify(u << 1, x);
			else modify(u << 1 | 1, x);
			pushup(u);
		}
	}
}T;

signed main() {
	cin >> n;
	for (int i = 0; i < 3; ++ i )
		for (int j = 1; j <= n; ++ j ) {
			char c;
			cin >> c;
			s[j][i] = c == '.';
		}
	T.build(1, 1, n);
	int q;
	cin >> q;
	
	while (q -- ) {
		int x, y;
		cin >> x >> y;
		s[y][x - 1] ^= 1;
		T.modify(1, y);
		int res = (Vector(0, INF, INF) * T.tr[1].v).a[2] - 1;
		cout << (res < 1e9 ? res : -1) << '\n';
	}
	return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void Tree::build(long long int, long long int, long long int)’:
Main.cpp:68:37: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   68 |                         int mid = l + r >> 1;
      |                                   ~~^~~
Main.cpp: In member function ‘void Tree::modify(long long int, long long int)’:
Main.cpp:77:43: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   77 |                         int mid = tr[u].l + tr[u].r >> 1;
      |                                   ~~~~~~~~^~~~~~~~~

Judge Result