Submission #1293461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293461		thuhienne	Crossing (JOI21_crossing)	C++20	100 / 100	990 ms	10584 KiB

Main

#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....
*/

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