Submission #702421

#	Time	Username	Problem	Language	Result	Execution time	Memory
702421		ld_minh4354	Crossing (JOI21_crossing)	C++17	0 / 100	113 ms	25932 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++) 
#define debug(x) cout<<#x<<" is " <<x<<endl;
typedef long long int ll;
const ll N=200010, MOD=(ll)1000000000000000009;
string A[4],T;
char ch;
ll n, Q,val[10],l,r,q,cur, mul[N], mmm[N];
ll jj(char x){
	if(x=='J')return 0;
	if(x=='O')return 1;
	return 2;
}
int jjj(char x, char y){
	if(x==y) return jj(x);
	else return (3-jj(x)-jj(y));
}
int jjjj(int x, int y){
	if(x==y) return x;
	else return (3-x-y);
}
ll convert(string x){
	ll ans=0;
	rep(i,n){
		//cout<<jj(x[i])*mul[i]<<' ';
		ans+=jj(x[i])*mul[i];
		ans%=MOD;
	}
	//cout<<endl;
	return ans;
}
ll conver(string x, string y){
	ll ans=0;
	rep(i,n){
		ans+=jjj(x[i],y[i])*mul[i];
		ans%=MOD;
	}
	return ans;
}
ll conve(string x, string y,string z){
	ll ans=0;
	rep(i,n){
		ans+=jjjj(jj(z[i]),jjj(x[i],y[i]))*mul[i];
		ans%=MOD;
	}
	return ans;
}
struct node{
	ll s,e,m,lazy,val;
	node *l, *r;
	node (int S, int E){
		s=S,e=E,m=(s+e)/2,val=0,lazy=-1;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void propogate(){
		if(lazy==-1) return;
		val=lazy*(mmm[e]-(s==0 ? 0: mmm[s-1]));//cout<<lazy<<' '<<mmm[e]-(s==0 ? 0: mmm[s-1])<<endl;
		if(s!=e){
			l->lazy=lazy;
			r->lazy=lazy;
		}
		lazy=-1;
	}
	void set(int S, int E, ll V){
		if(s==S&&e==E)lazy=V;
		else{
          propogate();
			if(E<=m)l->set(S,E,V);
			else if(m<S) r-> set(S,E,V);
			else l->set(S,m,V), r->set(m+1,E,V);
			l->propogate(), r->propogate();
			val=l->val+r->val;
		}
	}
	ll query(int S, int E){
		propogate();
		if(s==S&&e==E)return val;
		else if(E<=m) return l->query(S,E);
		else if(m<S) return r->query(S,E);
		else return l->query(S,m)+r->query(m+1,E);
	}
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n>>A[0]>>A[1]>>A[2]>>Q>>T;
	mul[0]=1;
	rep(i,n)mul[i+1]=(mul[i]*3)%MOD;
	mmm[0]=1;
	rep(i,n)mmm[i+1]=(mul[i+1]+mmm[i])%MOD;
	rep(i,3) val[i]=convert(A[i]);
	rep(i,3) val[i+3]=conver(A[i],A[(i+1)%3]);
	rep(i,3) val[i+6]=conve(A[i],A[(i+1)%3],A[(i+2)%3]);
	//rep(i,9)cout<<val[i]<<' ';cout<<endl;
	root= new node(0,200010);
	rep(i,n){
		//cout<<"set: "<<i<<endl;
		root->set(i,i,jj(T[i]));
	}
	ll cur=root->query(0,n);
	bool flag=true;
	rep(i,9){
		if(cur==val[i]){
			flag=false,cout<<"Yes\n";
			break;
		}
	}
	//rep(i,n)cout<<root->query(i,i)<<' ';
	if(flag)cout<<"No\n";
	while(Q--){
		cin>>l>>r>>ch;
		l--,r--;
		root->set(l,r,jj(ch));
		ll cur=root->query(0,n-1);
		//rep(i,n)cout<<root->query(i,i)<<' ';
		//cout<<cur<<' ';
		bool flag=true;
		rep(i,9)if(cur==val[i]){
			flag=false,cout<<"Yes\n";
			break;
		}
		if(flag)cout<<"No\n";
	}
}

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