Submission #547452

#	Time	Username	Problem	Language	Result	Execution time	Memory
547452		codr0	Crossing (JOI21_crossing)	C++14	100 / 100	414 ms	38620 KiB

Main

// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cerr<<#x<<" : "<<x<<'\n'
#define MOD(x) if(x>=M) x-=M; if(x<0) x+=M;

using namespace std;
	int to(char x0){
		if(x0=='J') return 0;
		if(x0=='O') return 1;
		return 2;
	}
struct node{
	int sz;
	int num;
};
const int BASE=3;
const int MOD=1000696969;
const int N=2e5+4;
int pw[N],n;
int ps_pw[N];
vector<int> hsh;
node seg[4*N];
int lazy[4*N];
bool lzy[4*N];
struct X{
	int a[N];
	void set(string x0){
		FOR(i,0,n-1){
			a[i]=to(x0[i]);
		}
	}
	int get_hsh(){
		int rt=0;
		FOR(i,0,n-1) rt=(rt+a[i]*pw[i])%MOD;
		rt=(rt+MOD)%MOD;
		return rt;
	}
};
	X merge(X a,X b){
		X rt;
		FOR(i,0,n-1){
			rt.a[i]=(9-a.a[i]-b.a[i])%3;
		}
		return rt;
	}

	void build(int id,int l,int r){
		seg[id].sz=r-l;
		seg[id].num=0;
		if(l+1==r) return;
		int mid=(r+l)/2;
		build(2*id,l,mid);
		build(2*id+1,mid,r);
	}

	node merge(node a,node b){
		node rt;
		rt.sz=a.sz+b.sz;
		rt.num=(a.num+pw[a.sz]*b.num)%MOD;
		return rt;
	}

	void shift(int id){
		if(!lzy[id]) return;
		lzy[id]=0;
		lzy[2*id]=1;
		lzy[2*id+1]=1;
		lazy[2*id]=lazy[id];
		lazy[2*id+1]=lazy[id];
		seg[2*id].num=(ps_pw[seg[2*id].sz-1]*lazy[id])%MOD;
		seg[2*id+1].num=(ps_pw[seg[2*id+1].sz-1]*lazy[id])%MOD;
	}

	void upd(int id,int l,int r,int st,int en,int X){
		if(st>=r||en<=l) return;
		if(st<=l&&en>=r){
			seg[id].num=(ps_pw[seg[id].sz-1]*X)%MOD;
			lzy[id]=1;
			lazy[id]=X;
			return;
		}
		shift(id);
		int mid=(r+l)/2;
		upd(2*id,l,mid,st,en,X);
		upd(2*id+1,mid,r,st,en,X);
		seg[id]=merge(seg[2*id],seg[2*id+1]);
	}
	
	void check(){
		int Y=(seg[1].num+MOD)%MOD;
		for(int u0:hsh){
			u0=(u0+MOD)%MOD;
			if(u0==Y){
				cout<<"Yes\n";
				return;
			}
		}
		cout<<"No\n";
		return;
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);	

	pw[0]=1; FOR(i,1,N-1) pw[i]=(pw[i-1]*BASE)%MOD;
	ps_pw[0]=1; FOR(i,1,N-1) ps_pw[i]=(ps_pw[i-1]+pw[i])%MOD;
	cin>>n;
	build(1,1,n+1);
	string x0;
	X A,B,C;
	cin>>x0;
	A.set(x0);
	cin>>x0;
	B.set(x0);
	cin>>x0;
	C.set(x0);
	X AB,BC,AC;
	AB=merge(A,B);
	AC=merge(A,C);
	BC=merge(B,C);
	X _C,_A,_B;
	_A=merge(A,BC);
	_B=merge(B,AC);
	_C=merge(C,AB);

	hsh.pb(A.get_hsh());
	hsh.pb(B.get_hsh());
	hsh.pb(C.get_hsh());
	hsh.pb(AB.get_hsh());
	hsh.pb(AC.get_hsh());
	hsh.pb(BC.get_hsh());
	hsh.pb(_A.get_hsh());
	hsh.pb(_B.get_hsh());
	hsh.pb(_C.get_hsh());

	int q; cin>>q;
	string W;
	cin>>W;
	FOR(i,0,n-1){
		upd(1,1,n+1,i+1,i+2,to(W[i]));
	}
	check();

	FOR(i,1,q){
		int l,r;
		char x0;
		cin>>l>>r>>x0;
		upd(1,1,n+1,l,r+1,to(x0));
		check();
	}




	return 0;
    }

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