제출 #1288956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288956		nikolashami	Crossing (JOI21_crossing)	C++20	100 / 100	147 ms	19576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

#pragma GCC optimize("O3")
const ll N=2e5+4,bs=1e5+3,mod=1e9+7,inv=540539193ll;
int a[9][N];
ll hsh[9],P[N],lik[N],n;

void sjebi(ll i,ll j,ll k){
	for(int l=1;l<=n;++l)
		a[k][l]=((a[i][l]+a[j][l])*2)%3;
}

struct node{
	ll H=0,lz=-1;
}st[11*N];

ll mrg(ll x,ll y,ll len){
	return(x*P[len]+y)%mod;
}

ll get(ll x,ll y){
	return(x*(P[y]-1ll)*inv)%mod;
}

void push(ll i,ll l,ll r){
	if(st[i].lz==-1)return;
	st[i*2].H=get(st[i].lz,(l+r)/2-l+1);
	st[i*2+1].H=get(st[i].lz,r-(l+r)/2);
	st[i*2].lz=st[i*2+1].lz=st[i].lz;
	st[i].lz=-1;
}

void bd(ll i=1,ll l=1,ll r=n){
	if(l==r){st[i].H=lik[l];return;}
	ll md=(l+r)/2;
	bd(i*2,l,md);
	bd(i*2+1,md+1,r);
	st[i].H=mrg(st[i*2].H,st[i*2+1].H,r-md);
}

void upd(ll l,ll r,ll x,ll i=1,ll tl=1,ll tr=n){
	//push(i,tl,tr);
	if(tl>=l&&tr<=r){
		st[i].lz=x;
		st[i].H=get(x,tr-tl+1);
		return;
	}
	push(i,tl,tr);
	ll md=(tl+tr)/2;
	if(l<=md)upd(l,r,x,i*2,tl,md);
	if(md+1<=r)upd(l,r,x,i*2+1,md+1,tr);
	st[i].H=mrg(st[i*2].H,st[i*2+1].H,tr-md);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int j=0;j<3;++j){
    	for(int i=1;i<=n;++i){
    		char c;cin>>c;
    		a[j][i]=(c=='O')+2*(c=='I');
    	}
	}

	//cout<<"A"<<endl;

	sjebi(0,1,3);
	sjebi(0,2,4);
	sjebi(1,2,5);
	sjebi(0,5,6);
	sjebi(1,4,7);
	sjebi(2,3,8);

	//cout<<"B"<<endl;

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

	for(int i=0;i<9;++i){
		hsh[i]=0;
		for(int j=1;j<=n;++j)
			hsh[i]=(hsh[i]*bs+a[i][j])%mod;
	}

	//cout<<"C"<<endl;

	set<ll>es;
	for(int i=0;i<9;++i)
		es.insert(hsh[i]);

	ll q;cin>>q;

	for(int i=1;i<=n;++i){
		char c;cin>>c;
		lik[i]=(c=='O')+2*(c=='I');
	}

	//cout<<"D"<<endl;

	bd();
	cout<<(es.find(st[1].H)==es.end()?"No\n":"Yes\n");

	//cout<<"E"<<endl;

	while(q--){
		ll l,r;char c;
		cin>>l>>r>>c;
		upd(l,r,(c=='O')+2*(c=='I'));
		cout<<(es.find(st[1].H)==es.end()?"No\n":"Yes\n");
	}

	//cout<<"F"<<endl;
}

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