Submission #534029

#	Time	Username	Problem	Language	Result	Execution time	Memory
534029		michao	Crossing (JOI21_crossing)	C++14	100 / 100	413 ms	20588 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<18;
const int STALA=2e5;
const int mod=1e9+9;
const int ALFABET=31;
int P[MAX];
set<string>cands;

string func(string a,string b){
	string ans="";
	for (int i=0;i<sz(a);i++){
		char c1=a[i],c2=b[i];
		if (c1==c2)ans+=c1;
		else if (c1=='J' && c2=='O')ans+='I';
		else if (c1=='O' && c2=='J')ans+='I';
		else if (c1=='J' && c2=='I')ans+='O';
		else if (c1=='I' && c2=='J')ans+='O';
		else if (c1=='O' && c2=='I')ans+='J';
		else if (c1=='I' && c2=='O')ans+='J';
	}
	return ans;
}

set<int>Hashes;

int make_hash(string s){
  int Hash=0;
	for (int i=1;i<=sz(s);i++){
		Hash=(Hash+P[i]*(s[i-1]-'A'))%mod;
	}
	return Hash;
}

char lazy[MAX*4];
int S[MAX*4];
int memo[MAX][3];

int conv(char x){
	if (x=='J')return 0;
	if (x=='O')return 1;
	if (x=='I')return 2;
	assert(false);
	return -1;
}

char merguj(char a,char b){
	if (b=='@')return a;
	return b;
}

void push(int u,int lo,int hi){
	if (lazy[u]!='@'){
		char lits=lazy[u];
		int suma=memo[hi-lo+1][conv(lits)];
	  suma=(suma*P[lo-1])%mod;
	  S[u]=suma;
	}
	S[u]%=mod;
	lazy[2*u]=merguj(lazy[2*u],lazy[u]);
	lazy[2*u+1]=merguj(lazy[2*u+1],lazy[u]);
	lazy[u]='@';
}

char lit[3]={'J','O','I'};
void update(int a,int b,int u,int lo,int hi,char lits){
	if (hi<a || lo>b)return;
	push(u,lo,hi);
	if (a<=lo && b>=hi){
		lazy[u]=lits;
		/*
	  int suma=memo[hi-lo+1][conv(lits)];
	  suma=(suma*P[lo-1])%mod;
	  lazy[u]=suma;*/
		return;
	}
	int mid=(lo+hi)>>1;
	update(a,b,2*u,lo,mid,lits);
	update(a,b,2*u+1,mid+1,hi,lits);
	push(2*u,lo,mid);
	push(2*u+1,mid+1,hi);
	S[u]=(S[2*u]+S[2*u+1])%mod;
}

int query(int a,int b,int u,int lo,int hi){
	if (hi<a || lo>b)return 0;
	push(u,lo,hi);
	if (a<=lo && b>=hi)return S[u];
	int mid=(lo+hi)>>1;
	int L=query(a,b,2*u,lo,mid);
	int R=query(a,b,2*u+1,mid+1,hi);
	return (L+R)%mod;
}

int n;

void check(){
	int x=S[1];
	assert(S[1]==query(1,n,1,1,MAX));
	//cout<<"TERAZ "<<x<<"\n";
	if (Hashes.find(x)!=Hashes.end())cout<<"Yes\n";
	else cout<<"No\n";
}


int32_t main(){
  BOOST;
	fill(lazy,lazy+4*MAX,'@');
  P[0]=1;
  for (int i=1;i<=MAX-1;i++)P[i]=(P[i-1]*ALFABET)%mod;
  
  for (int i=0;i<3;i++){
		int akt=0;
		for (int j=1;j<=MAX-1;j++){
			akt+=P[j]*(lit[i]-'A');
			akt%=mod;
			memo[j][i]=akt;
		}
  }	
  cin>>n;
  string s[3];
  cin>>s[0]>>s[1]>>s[2];
  cands.ins(s[0]);
  cands.ins(s[1]);
  cands.ins(s[2]);
  cands.ins(func(s[0],s[1]));
  cands.ins(func(s[1],s[2]));
  cands.ins(func(s[0],s[2]));
  cands.ins(func(s[0],func(s[1],s[2])));
  cands.ins(func(s[1],func(s[0],s[2])));
  cands.ins(func(s[2],func(s[0],s[1])));
  
  //for (auto it:cands)cout<<it<<" "<<make_hash(it)<<"\n";
  
  for (auto it:cands){
		Hashes.ins((make_hash(it))%mod);
  }
  int q;
  cin>>q;
  string t;
  cin>>t;
  for (int i=1;i<=sz(t);i++){
		update(i,i,1,1,MAX,t[i-1]);
  }
  check();
  for (int z=0;z<q;z++){
		int l,r;
		char c;
		cin>>l>>r>>c;
		update(l,r,1,1,MAX,c);
		check();
  }
  return 0; 
}

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