Submission #1362862

#TimeUsernameProblemLanguageResultExecution timeMemory
1362862Jawad_Akbar_JJCrossing (JOI21_crossing)C++20
0 / 100
0 ms440 KiB
#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<3;
vector<int> v[N<<1];
int eq[N<<1], lz[N<<1], l[N], r[N], id[N], Ans[N], n, q;
string S, T;
char C[N];

void Push(int cur, int lc, int rc, int x){
	if (lz[cur] == -1)
		return;

	x = lz[lc] = lz[rc] = lz[cur];
	eq[lc] = v[lc][x];
	eq[rc] = v[rc][x];
	lz[cur] = -1;

}

void replace(int l, int r, int x, int cur = 1, int st = 0, int en = N){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		lz[cur] = x;
		eq[cur] = v[cur][x];
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	Push(cur, lc, rc, 0);

	replace(l, r, x, lc, st, mid);
	replace(l, r, x, rc, mid, en);

	eq[cur] = eq[lc] + eq[rc];
}

void solve(){
	for (int i=1;i<N+N;i++)
		v[i] = {0, 0, 0}, eq[i] = 0, lz[i] = -1;

	for (int i=1;i<=n;i++)
		v[i+N][id[S[i-1]]] = 1;

	for (int i=N-1, lc = i + i, rc = lc + 1; i; i--, lc -= 2, rc -= 2)
		v[i] = {v[lc][0] + v[rc][0], v[lc][1] + v[rc][1], v[lc][2] + v[rc][2]};


	

	for (int i=1;i<=n;i++)
		replace(i, i+1, id[T[i-1]]);
	Ans[0] |= eq[1] == n;

	for (int i=1;i<=q;i++){
		replace(l[i], r[i]+1, id[C[i]]);
		Ans[i] |= eq[1] == n;
	}
}

string XOR(string a, string b){
	string c;
	int s = 'J' + 'O' + 'I';
	for (int i=0;i<a.size();i++){
		if (a[i] == b[i])
			c += a[i];
		else
			c += char(s - a[i] - b[i]);
	}
	return c;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	id['O'] = 1, id['I'] = 2;

	string a, b, c;

	cin>>n;
	cin>>a>>b>>c;

	cin>>q;
	cin>>T;

	for (int i=1;i<=q;i++)
		cin>>l[i]>>r[i]>>C[i];

	string A = XOR(a, b), B = XOR(a, c), C = XOR(b, c);
	string D = XOR(A, c), E = XOR(B, b), F = XOR(C, a);

	for (auto i : {a, b, c, A, B, C, D, E, F}){
		S = i;
		solve();
	}

	for (int i=0;i<=q;i++)
		cout<<(Ans[i] ? "YES\n" : "NO\n");
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...