제출 #1335788

#제출 시각아이디문제언어결과실행 시간메모리
1335788arkanefuryCrossing (JOI21_crossing)C++20
100 / 100
1127 ms22804 KiB
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define ins insert
#define lb lower_bound
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define sz size()
#define in insert
#define len(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N = 2e5 + 15;
int n, m, x, y, l, r, k, P = 7, mod = 1e9+7, ans[N], sum, cnt, a[N], b[N];
char c[N];
bool d1[N*6];
char d[N*6];
int t[N*6][3];
string s[4], sk, ss;
void push(int v, int l, int r){
	if(d[v] == ' ')return;
	if(l != r)d[v*2] = d[v*2+1] = d[v];
	if(d[v] == 'J'){
		if(t[v][0] == r-l+1)d1[v] = 1;
		
		else d1[v] = 0;
	}
	if(d[v] == 'O'){
		if(t[v][1] == r-l+1)d1[v] = 1;
		
		else d1[v] = 0;
	}
	if(d[v] == 'I'){
		if(t[v][2] == r-l+1)d1[v] = 1;
		else d1[v] = 0;
	}
	d[v] = ' ';
}
void build(int v = 1, int tl = 1, int tr = n){
		d[v] = ' ';
	if(tl == tr){
		if(ss[tl] == 'J')t[v][0] = 1, t[v][1] = t[v][2] = 0;
		else if(ss[tl] == 'O')t[v][1] = 1, t[v][0] = t[v][2] = 0;
		else t[v][2] = 1, t[v][1] = t[v][0] = 0;
		if(ss[tl] == sk[tl-1])d1[v] = 1;
		else d1[v] = 0;
		return;
	}
	int tm = (tl + tr) >> 1;
	build(v*2, tl, tm), build(v*2+1, tm+1, tr);
	t[v][0] = t[v*2][0] + t[v*2+1][0];
	t[v][1] = t[v*2][1] + t[v*2+1][1];
	t[v][2] = t[v*2][2] + t[v*2+1][2];
	d1[v] = (d1[v*2] & d1[v*2+1]);
}
void upd(int l, int r, char tp, int v = 1, int tl = 1, int tr = n){
	push(v, tl, tr);
	if(l <= tl && tr <= r){
		d[v] = tp;
		push(v, tl, tr);
		return;
	}
	if(l > tr || tl > r)return;
	int tm = (tl + tr) >> 1;
	upd(l, r, tp, v*2, tl, tm), upd(l, r, tp, v*2+1, tm+1, tr);
	d1[v] = (d1[v*2] & d1[v*2+1]);
}
string func(string s, string str){
	FOR(i, 0, s.sz-1, 1){
		if(s[i] != str[i]){
			if(s[i] != 'J' && str[i] != 'J')s[i] = 'J';
			else if(s[i] != 'O' && str[i] != 'O')s[i] = 'O';
			else s[i] = 'I';
		}
	}
	return s;
}
void solve(){
	vector<string>v;
	cin >> n >> s[1] >> s[2] >> s[3];
	cin >> m >> sk;
	char h;
	map<string, bool>mp;
	FOR(i, 1, 3, 1){
		string sok = s[i];
		FOR(j, 1, 3, 1){
				sok = func(sok, s[j]);
				mp[sok]=1;
		}
		FOR(ok, 1, 3, 1){
			sok = func(sok, s[ok]);
		mp[sok]=1;
		}
	}
	FOR(i, 1, m, 1)cin >> a[i] >> b[i] >> c[i];
	for(auto j : mp){
		ss='='+j.F;
		build();
		if(d1[1] == 1)ans[0] = 1;
		FOR(i, 1, m, 1){
			upd(a[i], b[i], c[i]);
			if(d1[1] == 1)ans[i] = 1;
		}
	}
	FOR(i, 0, m, 1){
		cout << (ans[i] == 1 ? "Yes\n" : "No\n");
	}
}
signed main(){
	nikita
	int t=1;
	// cin >> t;
	while(t--)solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...