Submission #1293461

#TimeUsernameProblemLanguageResultExecution timeMemory
1293461thuhienneCrossing (JOI21_crossing)C++20
100 / 100
990 ms10584 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define thuhien ""

int n,q;
vector <string> dna;
map <string,bool> freq;

string sa,sb,sc;

string merge(string& a,string& b) {
	string ret = " ";
	for (int i = 1;i <= n;i++) {
		if (a[i] == b[i]) ret.push_back(a[i]);
		if ((a[i] == 'J' && b[i] == 'O') || (b[i] == 'J' && a[i] == 'O')) ret.push_back('I');
		if ((a[i] == 'J' && b[i] == 'I') || (b[i] == 'J' && a[i] == 'I')) ret.push_back('O');
		if ((a[i] == 'I' && b[i] == 'O') || (b[i] == 'I' && a[i] == 'O')) ret.push_back('J');
	}
	return ret;
}

string start,aim;
struct {
	int l,r;
	char c;
} query[200009];

bool answer[200009];


int lt[200009];

bool st[200009 * 4];
char lazy[200009 * 4];

void build(int id,int l,int r) {
	lazy[id] = '?';
	if (l == r) {
		st[id] = start[l] == aim[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	st[id] = st[id*2] & st[id*2+1];
}

void changenode(int id,int l,int r,char c) {
	st[id] = (lt[r] <= l && aim[r] == c);
	lazy[id] = c;
}

void push_down(int id,int l,int r,int mid) {
	if (lazy[id] == '?') return;
	changenode(id*2,l,mid,lazy[id]);
	changenode(id*2+1,mid+1,r,lazy[id]);
	lazy[id] = '?';
}

void update(int id,int l,int r,int u,int v,char c) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		changenode(id,l,r,c);
		return;
	}
	int mid = (l + r) >> 1;
	push_down(id,l,r,mid);
	update(id*2,l,mid,u,v,c);
	update(id*2+1,mid+1,r,u,v,c);
	st[id] = st[id*2] & st[id*2+1];
}

void calc() {
	lt[1] = 1;
	for (int i = 2;i <= n;i++) {
		if (aim[i] == aim[i - 1]) lt[i] = lt[i - 1];
		else lt[i] = i;
	}
	build(1,1,n);
	answer[0] |= st[1];
	for (int i = 1;i <= q;i++) {
		update(1,1,n,query[i].l,query[i].r,query[i].c);
		answer[i] |= st[1];
	}
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  if (fopen(thuhien".inp","r")) {
//     freopen(thuhien".inp","r",stdin);
//     freopen(thuhien".out","w",stdout);
//  }
	cin >> n >> sa >> sb >> sc;
	sa = " " + sa,sb = " " + sb,sc = " " + sc;
	dna = {sa,sb,sc};
	freq[sa] = freq[sb] = freq[sc] = 1;
	
	while (true) {
		bool newgene = 0;
		for (int i = 0;i < dna.size();i++) {
			for (int j = i + 1;j < dna.size();j++) {
				string curr = merge(dna[i],dna[j]);
				if (!freq[curr]) {
					newgene = 1;
					freq[curr] = 1;
					dna.push_back(curr);
				}
			}
		}
		if (!newgene) break;
//		for (auto x : dna) cout << x << " ";
//		cout << '\n';
	}
	
	cin >> q >> start;
	start = " " + start;
	for (int i = 1;i <= q;i++) cin >> query[i].l >> query[i].r >> query[i].c;

	for (auto x : dna) {
//		cout << x << '\n';
		aim = x;
		calc();
	}
	
	for (int i = 0;i <= q;i++) cout << (answer[i] ? "Yes" : "No") << '\n';

}

/*
  Xach ba lo va di
  Nhin that xa ve noi cuoi phia con duong
  Khong lo ngay mai
  Bao kho khan ta buoc qua
  Dau cuoi doi nay rong bao la
  Ngay mai se tot thoi ma
  Bao may mu giong sao niu chan ta dau cuoc doi nay....
*/

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...