Submission #440426

#	Time	Username	Problem	Language	Result	Execution time	Memory
440426		Sohsoh84	Crossing (JOI21_crossing)	C++14	100 / 100	683 ms	40552 KiB

Main

// ¯\_(ツ)_/¯
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

vector<array<int, 3>> C = {
	{1, 0, 0},
	{0, 1, 0},
	{0, 0, 1},
	{2, 2, 0},
	{2, 0, 2},
	{0, 2, 2},
	{2, 1, 1},
	{1, 2, 1},
	{1, 1, 2}
};

int A[MAXN][9], n, q, T[MAXN][9], S[MAXN], lz[MAXN];
bool sg[MAXN][9];
string s1, s2, s3, s;

int Cnv(char c) {
	if (c == 'J') return 0;
	if (c == 'O') return 1;
	return 2;
}

void Build(int v, int L, int R) {
	if (L == R) {
		for (int j = 0; j < 9; j++) {
			T[v][j] = A[L][j];
			if (S[L] == A[L][j]) sg[v][j] = true;
		}

		return;
	}

	int mid = (L + R) >> 1;
	Build(v << 1, L, mid);
	Build(v << 1 | 1, mid + 1, R);
	
	for (int i = 0; i < 9; i++) {
		if (T[v << 1][i] == T[v << 1 | 1][i]) T[v][i] = T[v << 1][i];
		else T[v][i] = 4;
		sg[v][i] = sg[v << 1][i] & sg[v << 1 | 1][i];
	}
}

inline void Push(int v) {
	if (lz[v] < 0) return;
	for (int i = 0; i < 9; i++) sg[v][i] = (T[v][i] == lz[v]);
	
	if ((v << 1 | 1) < MAXN) lz[v << 1] = lz[v << 1 | 1] = lz[v];
	lz[v] = -1;
}

void Update(int v, int L, int R, int QL, int QR, int val) {
	Push(v);
	if (QR < QL) return;
	if (QL == L && QR == R) {
		lz[v] = val;
		Push(v);
		return;
	}

	int mid = (L + R) >> 1;
	Update(v << 1, L, mid, QL, min(QR, mid), val);
	Update(v << 1 | 1, mid + 1, R, max(QL, mid + 1), QR, val);
	for (int i = 0; i < 9; i++) sg[v][i] = sg[v << 1][i] & sg[v << 1 | 1][i];
}

inline int Print() {
	for (int i = 0; i < 9; i++) 
		if (sg[1][i])
			return cout << "Yes" << endl, 0;
	return cout << "No" << endl, 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> s1 >> s2 >> s3;
	for (int i = 1; i <= n; i++) {
		int a[3] = {Cnv(s1[i - 1]), Cnv(s2[i - 1]), Cnv(s3[i - 1])};
		for (int j = 0; j < 9; j++) {
			for (int k = 0; k < 3; k++) A[i][j] += C[j][k] * a[k];
			A[i][j] %= 3;
		}
	}

	cin >> q >> s;
	for (int i = 1; i <= n; i++) S[i] = Cnv(s[i - 1]);	
	Build(1, 1, n);
	fill(lz, lz + MAXN, -1);

	Print();
	while (q--) {
		int L, R;
		char c;
		cin >> L >> R >> c;
		Update(1, 1, n, L, R, Cnv(c));	
		Print();
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51