제출 #1342945

#제출 시각아이디문제언어결과실행 시간메모리
1342945blacktulipCrossing (JOI21_crossing)C++20
100 / 100
1112 ms53308 KiB
//Hello!..
//dört böler altı artı iki ama ne böler altı ne böler iki
//Başarı, Boş Duranın Hakkı Değil... Koşturanın Hakkıdır. Hakan?
//Ne yapayım, elimden gelen bu :(
//S'il vous plait
#include <bits/stdc++.h>
using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define pb push_back
//~ #define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define setrandom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrandom(a,b) uniform_int_distribution<int>(a,b)(rng)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 200002;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,tree[li*4][9],farkli[li*4][9],lazy[li*4][9];
int cev;
string s[9],ss;
vector<int> v;
map<string,int> vis;

inline string merge(string &s1,string &s2){
	string st;
	for(int i=0;i<n;i++){
		if(s1[i]==s2[i])st+=s1[i];
		else{
			int var=0;
			if(s1[i]=='I' || s2[i]=='I')var|=1;
			if(s1[i]=='J' || s2[i]=='J')var|=2;
			if(s1[i]=='O' || s2[i]=='O')var|=4;
			if(var==3)st+='O';
			if(var==5)st+='J';
			if(var==6)st+='I';
		}
	}
	return st;
}

inline void build(int node,int start,int end,int x){
	if(start==end){tree[node][x]=s[x][start]==ss[start];return ;}
	build(node*2,start,mid,x),build(node*2+1,mid+1,end,x);
	tree[node][x]=tree[node*2][x]&tree[node*2+1][x];
	farkli[node][x]=farkli[node*2][x]|farkli[node*2+1][x];
	if(s[x][mid]!=s[x][mid+1])farkli[node][x]=1;
	//~ cerr<<node _ x _ start _ end _ farkli[node][x] _ "AA\n";
}

inline void push(int node,int start,int end,int x){
	if(farkli[node][x]==0 && a[(int)s[x][start]]==lazy[node][x])tree[node][x]=1;
	else tree[node][x]=0;
	//~ cerr<<node _ x _ start _ end _ tree[node][x] _ lazy[node][x] _ "AA\n";
	if(start!=end){
		lazy[node*2][x]=lazy[node][x];
		lazy[node*2+1][x]=lazy[node][x];
	}
	lazy[node][x]=0;
}

inline void update(int node,int start,int end,int l,int r,int x,int v){
	if(lazy[node][x])push(node,start,end,x);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){lazy[node][x]=v;push(node,start,end,x);return ;}
	update(node*2,start,mid,l,r,x,v);
	update(node*2+1,mid+1,end,l,r,x,v);
	tree[node][x]=tree[node*2][x]&tree[node*2+1][x];
}

int32_t main(){
	fio();
	cin>>n;
	cin>>s[0]>>s[1]>>s[2];
	a['O']=1;
	a['J']=2;
	a['I']=3;
	//~ for(int i=0;i<n;i++){
		//~ if(s[0])
	//~ }
	vector<string > vv;
	vv.pb(s[0]);
	vv.pb(s[1]);
	vv.pb(s[2]);
	int ind=3;
	vis[s[0]]=1;
	vis[s[1]]=1;
	vis[s[2]]=1;
	for(int j=1;j<=2;j++){
		for(int i=0;i<(int)vv.size();i++){
			for(int j=i+1;j<(int)vv.size();j++){
				string st=merge(vv[i],vv[j]);
				if(vis.find(st)==vis.end()){vis[st]=1;s[ind++]=st;vv.pb(st);}
			}
		}
	}
	cin>>t>>ss;
	for(int j=0;j<(int)vv.size();j++)build(1,0,n-1,j);
	flag=0;
	for(int j=0;j<(int)vv.size();j++)if(tree[1][j])flag=1;
	if(flag)cout<<"Yes\n";
	else cout<<"No\n";
	while(t--){
		int l,r;
		char c;
		cin>>l>>r>>c;
		l--;
		r--;
		for(int j=0;j<(int)vv.size();j++){
			update(1,0,n-1,l,r,j,a[(int)c]);
		}
		flag=0;
		for(int j=0;j<(int)vv.size();j++){
			if(lazy[1][j])push(1,0,n-1,j);
			if(tree[1][j])flag=1;
		}
		if(flag)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...