Submission #916266

#	Time	Username	Problem	Language	Result	Execution time	Memory
916266		amirhoseinfar1385	Crossing (JOI21_crossing)	C++17	100 / 100	489 ms	21584 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long check(long long mid){
	for(long long i=2;i*i<=mid;i++){
		if(mid%i==0){
			return 0;
		}
	}
	return 1;
}

long long fiav(long long mid){
	while(check(mid)){
		mid++;
	}
	return mid;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long mod=fiav(rng()%1000000+999999000),base=fiav(rng()%100+5);
const long long maxn=200000+10;
vector<string>alls;
set<long long>allh;
long long n,q,mp[maxn],bh[maxn];

void aval(){
	mp[0]=1;
	bh[0]=1;
	for(long long i=1;i<maxn;i++){
		mp[i]=1ll*mp[i-1]*base%mod;
		bh[i]=bh[i-1]+mp[i];
		bh[i]%=mod;
	}
}

long long geth(string s){
	long long ret=0;
	for(long long i=0;i<n;i++){
		ret+=mp[i]*(s[i]-'a'+1)%mod;
		ret%=mod;
	}
	return ret;
}

string gets(string a,string b){
	string ret;
	ret.resize(n);
	for(long long i=0;i<n;i++){
		if(a[i]==b[i]){
			ret[i]=a[i];
		}
		else{
			ret[i]='a'^'b'^'c'^a[i]^b[i];
		}
	}
	return ret;
}

void tagh(string &s){
	for(long long i=0;i<n;i++){
		if(s[i]=='J'){
			s[i]='a';
		}
		else if(s[i]=='O'){
			s[i]='b';
		}
		else{
			s[i]='c';
		}
	}
}

long long upd(){
	vector<string>fake;
	long long f=0;
	for(long long i=0;i<(long long)alls.size();i++){
		for(long long j=i+1;j<(long long)alls.size();j++){
			string s=gets(alls[i],alls[j]);
			long long sh=geth(s);
			if((long long)allh.count(sh)==0){
				f=1;
				allh.insert(sh);
				fake.push_back(s);
				//cout<<"wtf: "<<sh<<" "<<s<<endl;
			}
		}
	}
	for(auto x:fake){
		alls.push_back(x);
	}
	return f;
}
string now;
long long hnow;
set<pair<long long,pair<long long,char>>>allind;

void ins(long long l,long long r,char c){
	hnow+=bh[r-l]*mp[l]*(c-'a'+1)%mod;
	hnow%=mod;
	allind.insert(make_pair(l,make_pair(r,c)));
}

void erase(long long l,long long r,char c){
	hnow+=mod+mod-(bh[r-l]*mp[l]*(c-'a'+1)%mod);
	hnow%=mod;
	allind.erase(make_pair(l,make_pair(r,c)));
}	

void updq(long long l,long long r,char c){
	while((long long)allind.size()>0&&(*allind.rbegin()).first>=l){
		auto x=*allind.lower_bound(make_pair(l,make_pair(0,0)));
		if(x.first<=r&&x.second.first<=r){
			erase(x.first,x.second.first,x.second.second);
			continue;
		}
		if(x.first<=r){
			erase(x.first,x.second.first,x.second.second);
			ins(r+1,x.second.first,x.second.second);
			continue;
		}
		break;
	}
	if((long long)allind.size()>0&&(*allind.begin()).first<l){
		auto y=allind.lower_bound(make_pair(l,make_pair(0,0)));
		y--;
		auto x=*y;
		if(x.second.first>r){
			erase(x.first,x.second.first,x.second.second);
			ins(x.first,l-1,x.second.second);
			ins(r+1,x.second.first,x.second.second);
		}
		else if(x.second.first>=l){
			erase(x.first,x.second.first,x.second.second);
			ins(x.first,l-1,x.second.second);
		}
	}
	ins(l,r,c);
}

void khor(){
	//cout<<hnow<<endl;
	if(allh.count(hnow)==1){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	aval();
	cin>>n;
	alls.resize(3);
	cin>>alls[0]>>alls[1]>>alls[2];
	tagh(alls[0]);
	tagh(alls[1]);
	tagh(alls[2]);
	while(upd()){
		//hehecalackhordy
	}
	cin>>q;
	cin>>now;
	tagh(now);
	//cout<<"tof: "<<now<<endl;
	for(long long i=0;i<n;i++){
		ins(i,i,now[i]);
	}
	khor();
	for(long long i=0;i<q;i++){
		long long l,r;
		char c;
		cin>>l>>r>>c;
		l--;
		r--;
		if(c=='J'){
			c='a';
		}
		else if(c=='O'){
			c='b';
		}
		else{
			c='c';
		}
		updq(l,r,c);
		khor();
	}
}

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