Submission #440547

#TimeUsernameProblemLanguageResultExecution timeMemory
440547ogibogi2004Crossing (JOI21_crossing)C++14
100 / 100
2384 ms27372 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
vector<string>p;
int n;
string cross(string s1,string s2)
{
	string ret="";
	for(int i=0;i<s1.size();i++)
	{
		if(s1[i]==s2[i])ret+=s1[i];
		else ret+=char('J'+'O'+'I'-s1[i]-s2[i]);
	}
	return ret;
}
bool tree[9][3*MAXN];
char lazy[9][3*MAXN];
char tree1[9][3*MAXN];
bool pushed[9][3*MAXN];
void push_lazy(int l,int r,int idx)
{
	for(int j=0;j<9;j++)
	{
		if(pushed[j][idx])continue;
		if(tree1[j][idx]==lazy[j][idx])tree[j][idx]=1;
		else tree[j][idx]=0;
		pushed[j][idx]=1;
		if(l!=r)
		{
			pushed[j][idx*2]=0;
			pushed[j][idx*2+1]=0;
			lazy[j][idx*2]=lazy[j][idx];
			lazy[j][idx*2+1]=lazy[j][idx];
		}
	}
}
void build(int l,int r,int idx)
{
	if(l==r)
	{
		for(int j=0;j<9;j++)tree1[j][idx]=p[j][l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,idx*2);
	build(mid+1,r,idx*2+1);
	for(int j=0;j<9;j++)
	{
		if(tree1[j][idx*2]==tree1[j][idx*2+1])
		{
			tree1[j][idx]=tree1[j][idx*2];
		}
		else tree1[j][idx]='o';
	}
}
void update(int l,int r,int idx,int ql,int qr,char val)
{
	//cout<<l<<" "<<r<<" "<<idx<<endl;
	push_lazy(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		for(int j=0;j<9;j++)
		{
			lazy[j][idx]=val;
			pushed[j][idx]=0;
		}
		push_lazy(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update(l,mid,idx*2,ql,qr,val);
	update(mid+1,r,idx*2+1,ql,qr,val);
	for(int j=0;j<9;j++)
	{
		tree[j][idx]=(tree[j][idx*2]&tree[j][idx*2+1]);
	}
}
void print(int l,int r,int idx,int idx1)
{
	cout<<l<<" "<<r<<" "<<tree[idx1][idx]<<endl;
	if(l==r)return;
	int mid=(l+r)/2;
	print(l,mid,idx*2,idx1);
	print(mid+1,r,idx*2+1,idx1);
}
int main()
{
	memset(pushed,1,sizeof(pushed));
	cin>>n;
	string s;
	cin>>s;
	s=" "+s;
	p.push_back(s);
	cin>>s;
	s=" "+s;
	p.push_back(s);
	cin>>s;
	s=" "+s;
	p.push_back(s);
	p.push_back(cross(p[0],p[1]));
	p.push_back(cross(p[2],p[1]));
	p.push_back(cross(p[0],p[2]));
	p.push_back(cross(cross(p[0],p[2]),p[1]));
	p.push_back(cross(cross(p[0],p[1]),p[2]));
	p.push_back(cross(cross(p[2],p[1]),p[0]));
	/*cout<<"p:\n";
	for(int i=0;i<p.size();i++)cout<<p[i]<<endl;
	cout<<"\n^\n";*/
	build(1,n,1);
	int q;
	cin>>q;
	cin>>s;
	s=" "+s;
	for(int i=1;i<s.size();i++)
	{
		update(1,n,1,i,i,s[i]);
	}
	bool ans=0;
	ans=0;
	for(int j=0;j<9;j++)
	{
		ans=(ans|tree[j][1]);
	}
	if(ans)cout<<"Yes\n";
	else cout<<"No\n";
	for(int i=0;i<q;i++)
	{
		int l,r;
		char c;
		cin>>l>>r;cin>>c;
		update(1,n,1,l,r,c);
		ans=0;
		for(int j=0;j<9;j++)
		{
			ans=(ans|tree[j][1]);
		}
		/*for(int j=0;j<9;j++)
		{
			cout<<j<<":\n";
			print(1,n,1,j);
		}*/
		if(ans)cout<<"Yes\n";
		else cout<<"No\n";
	}
return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:9:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for(int i=0;i<s1.size();i++)
      |              ~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i=1;i<s.size();i++)
      |              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...