제출 #425418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425418		CSQ31	Crossing (JOI21_crossing)	C++14	26 / 100	562 ms	63348 KiB

Main

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e5+5;
string make(string a,string b){
	int n = sz(a);
	string res(n,'a');
	for(int i=0;i<n;i++){
		if(a[i] == b[i])res[i] = a[i];
		else{
			if((a[i] == 'I' && b[i] == 'O') || (a[i] == 'O' && b[i] == 'I'))res[i] = 'J';
			if((a[i] == 'J' && b[i] == 'I') || (a[i] == 'I' && b[i] == 'J'))res[i] = 'O';
			if((a[i] == 'O' && b[i] == 'J') || (a[i] == 'J' && b[i] == 'O'))res[i] = 'I';
			
		}
	}
	return res;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll MOD[2],pw[2][MAXN];
ll base;
PII hh(string s){
	PII res = {0,0};
	for(int i=0;i<sz(s);i++){
		res.fi+=((s[i]-'A')*pw[0][i])%MOD[0];
		res.se+=((s[i]-'A')*pw[1][i])%MOD[1];
		if(res.fi>=MOD[0])res.fi-=MOD[0];
		if(res.se>=MOD[1])res.se-=MOD[1];
	}
	return res;
}
ll binpow(ll n,ll k,ll mod){
	ll res = 1;
	while(k){
		if(k&1)res*=n;
		n*=n;
		k/=2;
		res%=mod;
		n%=mod;
	}
	return res;
}
vector<vector<PII>> pref(4,vector<PII>(MAXN));
vector<PII>t(4*MAXN);
vector<int>lazy(MAXN,-1);
void pushdown(int v,int l,int r){
	int tm = (l+r)/2;
	if(lazy[v] != -1){
		int c = lazy[v];
		lazy[2*v] = lazy[2*v+1] = c;
		t[2*v].fi = (pref[c][tm].fi - pref[c][l-1].fi+MOD[0])%MOD[0];
		t[2*v].se = (pref[c][tm].se - pref[c][l-1].se+MOD[1])%MOD[1];
		t[2*v+1].fi = (pref[c][r].fi - pref[c][tm].fi+MOD[0])%MOD[0];
		t[2*v+1].se = (pref[c][r].se - pref[c][tm].se+MOD[1])%MOD[1];
		lazy[v] = -1;
	}
}
void upd(int v,int l,int r,int tl,int tr,int c){
	if(l > r)return;
	if(l == tl && r == tr){
		lazy[v] = c;
		t[v].fi = (pref[c][r].fi - pref[c][l-1].fi+MOD[0])%MOD[0];
		t[v].se = (pref[c][r].se - pref[c][l-1].se+MOD[1])%MOD[1];	
		return;	
	}
	pushdown(v,tl,tr);
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,c);
	upd(2*v+1,max(tm+1,l),r,tm+1,tr,c);
	t[v].fi = (t[2*v].fi+t[2*v+1].fi)%MOD[0];
	t[v].se = (t[2*v].se+t[2*v+1].se)%MOD[1];
}
PII query(int v,int l,int r,int tl,int tr){
	if(l>r)return {0,0};
	if(l==tl && r==tr){
		return t[v];
	}
	int tm =(tl+tr);
	pushdown(v,tl,tr);
	PII a = query(2*v,l,min(r,tm),tl,tm);
	PII b = query(2*v+1,max(tm+1,l),r,tm+1,tr);
	return {(a.fi+b.fi)%MOD[0],(a.se+b.se)%MOD[1]};
}


int main()
{
	int n,q;
	cin>>n;
	MOD[0] = 1e9+7;
	MOD[1] = uniform_int_distribution<ll>(1e9+7,1e10)(rng);
	base = uniform_int_distribution<ll>(1e6,1e9+6)(rng);
	pw[0][0] = pw[1][0] = 1;
	for(int i=0;i<2;i++)
		for(int j=1;j<n;j++)pw[i][j] = pw[i][j-1] * base %MOD[i];
		
		
	string a,b,c,t;
	cin>>a>>b>>c>>q>>t;
	vector<string>cur = {a,b,c};
	set<PII>seen;
	seen.insert(hh(a));
	seen.insert(hh(b));
	seen.insert(hh(c));
	int idx=0;
	while(true){
		vector<string>tmp;
		bool ok =0;
		for(int i=idx+1;i<sz(cur);i++){
			string res = make(cur[idx],cur[i]);
			PII r = hh(res);
			if(!seen.count(r)){
				ok = 1;
			   seen.insert(r);
			   cur.pb(res);
		   }
		}
		idx++;
		if(!ok)break;
	}
	string J = "JOI";
	for(int i=0;i<3;i++){
		for(int j=1;j<=n;j++){
			pref[i][j].fi+=((J[i]-'A')*pw[0][j-1])%MOD[0];
			pref[i][j].se+=((J[i]-'A')*pw[1][j-1])%MOD[1];
			pref[i][j].fi+=pref[i][j-1].fi;
			pref[i][j].se+=pref[i][j-1].se;
			if(pref[i][j].fi>=MOD[0])pref[i][j].fi-=MOD[0];
			if(pref[i][j].se>=MOD[1])pref[i][j].se-=MOD[1];
			
		}
	}
	for(int i=1;i<=n;i++){
		pref[3][i].fi+=pref[3][i-1].fi;
		pref[3][i].se+=pref[3][i-1].se;
		pref[3][i].fi+=(t[i-1]-'A')*pw[0][i-1]%MOD[0];
		pref[3][i].se+=(t[i-1]-'A')*pw[1][i-1]%MOD[1];
		pref[3][i].fi%=MOD[0];
		pref[3][i].se%=MOD[1];
	}
	upd(1,1,n,1,n,3);
	if(seen.count(query(1,1,n,1,n)))cout<<"Yes"<<'\n';
	else cout<<"No"<<'\n';
	while(q--){
		int l,r;
		char c;
		cin>>l>>r>>c;
		if(c=='J')upd(1,l,r,1,n,0);
		if(c=='O')upd(1,l,r,1,n,1);
		if(c=='I')upd(1,l,r,1,n,2);
		PII nw = query(1,1,n,1,n);
		if(seen.count(nw))cout<<"Yes"<<'\n';
		else cout<<"No"<<'\n';
		//divide by base^l :waturr: need inverse
	}
	//cout<<sz(seen)<<'\n';
}

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