Submission #717860

#	Time	Username	Problem	Language	Result	Execution time	Memory
717860		Radin_Zahedi2	Crossing (JOI21_crossing)	C++17	100 / 100	521 ms	26360 KiB

Main

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n;
const int N = 2e5 + 5;
const int L = (1 << 19);
const int possi[9][3] = {{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}};
bool seg[L][4][9];
int lazy[L];

string s[3];

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

	return -1;
}

void applyind(int ind, int c) {
	for (int f = 0; f < 9; f++) {
		seg[ind][3][f] = seg[ind][c][f];
	}
	lazy[ind] = c;
}

void apply(int ind) {
	if (lazy[ind] != -1) {
		applyind(2 * ind, lazy[ind]);
		applyind(2 * ind + 1, lazy[ind]);

		lazy[ind] = -1;
	}
}

void cre(int l, int r, int ind) {
	if (l == r) {
		for (int f = 0; f < 9; f++) {
			int c = 0;

			for (int st = 0; st < 3; st++) {
				c += possi[f][st] * inted(s[st][l]);
			}

			seg[ind][c % 3][f] = true;
		}

		lazy[ind] = -1;

		return;
	}


	int m = (l + r) / 2;
	cre(l, m, 2 * ind);
	cre(m + 1, r, 2 * ind + 1);

	for (int c = 0; c < 4; c++) {
		for (int f = 0; f < 9; f++) {
			seg[ind][c][f] = (seg[2 * ind][c][f] && seg[2 * ind + 1][c][f]);
		}
	}

	lazy[ind] = -1;
}

void upd(int b, int e, int c, int l, int r, int ind) {
	if (b <= l && r <= e) {
		applyind(ind, c);

		return;
	}
	if (e < l || r < b) {
		return;
	}


	apply(ind);

	int m = (l + r) / 2;
	upd(b, e, c, l, m, 2 * ind);
	upd(b, e, c, m + 1, r, 2 * ind + 1);

	for (int f = 0; f < 9; f++) {
		seg[ind][3][f] = (seg[2 * ind][3][f] && seg[2 * ind + 1][3][f]);
	}
}

void answ() {
	for (int f = 0; f < 9; f++) {
		if (seg[1][3][f]) {
			cout << "Yes" << endl;
			return;
		}
	}

	cout << "No" << endl;
}

void init() {
}

void input() {
	cin >> n;

	cin >> s[0] >> s[1] >> s[2];
}

void solve() {
	cre(0, n - 1, 1);

	int q;
	cin >> q;

	string t;
	cin >> t;

	for (int i = 0; i < n; i++) {
		upd(i, i, inted(t[i]), 0, n - 1, 1);
	}

	answ();


	while (q--) {
		int b, e;
		char c;
		cin >> b >> e >> c;

		upd(b - 1, e - 1, inted(c), 0, n - 1, 1);

		answ();
	}
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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