Submission #1156733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156733		alexander707070	Crossing (JOI21_crossing)	C++20	100 / 100	190 ms	43808 KiB

Main

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,l,r,q,a[MAXN];
char c;
vector<int> s[4],w;

const long long mod[2]={1000000007,1000000009};

long long power[MAXN][2];

void precalc(){
	power[0][0]=power[0][1]=1;

	for(int i=1;i<=n;i++){
		power[i][0]=(power[i-1][0]*4)%mod[0];
		power[i][1]=(power[i-1][1]*4)%mod[1];
	}
}

struct hesh{
	long long h[2]={0,0};
	int len=0;

	void add(int x){
		h[0]*=4; h[0]+=x+1; h[0]%=mod[0];
		h[1]*=4; h[1]+=x+1; h[1]%=mod[1];
		len++;
	}

	inline friend bool operator == (hesh fr,hesh sc){
		return fr.h[0]==sc.h[0] and fr.h[1]==sc.h[1];
	}

	inline friend hesh operator + (hesh fr,hesh sc){
		return { (fr.h[0]*power[sc.len][0] + sc.h[0])%mod[0] , (fr.h[1]*power[sc.len][1] + sc.h[1])%mod[1] , fr.len+sc.len };
	}
}special[3][MAXN],pref[3];

struct SegmentTree{
	hesh tree[4*MAXN];
	int lazy[4*MAXN];

	void build(int v,int l,int r){
		if(l==r)tree[v].add(a[l]);
		else{
			int tt=(l+r)/2;

			build(2*v,l,tt);
			build(2*v+1,tt+1,r);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}

	void psh(int v){
		if(lazy[v]==0)return;

		tree[2*v]=special[lazy[v]-1][tree[2*v].len];
		tree[2*v+1]=special[lazy[v]-1][tree[2*v+1].len];

		lazy[2*v]=lazy[2*v+1]=lazy[v];
		lazy[v]=0;
	}

	void update(int v,int l,int r,int ll,int rr,int val){
		if(ll>rr)return;
		if(l==ll and r==rr){
			tree[v]=special[val][tree[v].len];
			lazy[v]=val+1;
		}else{
			int tt=(l+r)/2;
			psh(v);

			update(2*v,l,tt,ll,min(tt,rr),val);
			update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}
}seg;

int val(char c){
	if(c=='J')return 0;
	if(c=='O')return 1;
	if(c=='I')return 2;
}

vector<hesh> vals;

hesh calc(vector<int> s){

	hesh res;
	for(int i=0;i<n;i++)res.add(s[i]);

	return res;
}

void dumb(){
	for(int i=0;i<3;i++){
		for(int f=0;f<3;f++){
			for(int k=0;k<3;k++){

				if(i+f+k==1 or i+f+k==4){
					for(int d=0;d<n;d++)w.push_back((i*s[1][d]+f*s[2][d]+k*s[3][d])%3);
					vals.push_back(calc(w));
					w.clear();
				}

			}
		}
	}
}

void query(){
	hesh curr=seg.tree[1];

	for(auto z:vals){
		if(z==curr){
			cout<<"Yes\n";
			return;
		}
	}

	cout<<"No\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	for(int i=1;i<=3;i++){
		for(int f=1;f<=n;f++){
			cin>>c;
			s[i].push_back(val(c));
		}
	}

	precalc();
	dumb();

	for(int i=1;i<=n;i++){
		for(int f=0;f<3;f++)pref[f].add(f);
		for(int f=0;f<3;f++)special[f][i]=pref[f];
	}

	cin>>q;
	for(int i=1;i<=n;i++){
		cin>>c;
		a[i]=val(c);
	}

	seg.build(1,1,n);
	query();

	for(int i=1;i<=q;i++){
		cin>>l>>r>>c;

		seg.update(1,1,n,l,r,val(c));
		query();
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int val(char)':
Main.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

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