제출 #521118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521118		new_acc	Crossing (JOI21_crossing)	C++14	100 / 100	872 ms	17744 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const ll mod=1000*1000*1000+7;
const ll p=70032301;
const int SS=1<<19;
unordered_map<ll,bool> m;
vector<string> v;
ll seg[SS*2+10],lazy[SS*2+10];
ll sum[N],pot[N];
ll ustaw(int l,int r,ll x){
	return (sum[r-l]*x)%mod;
}
void push(int v,int l,int r){
	if(lazy[v]==0) return;
	seg[v*2]=ustaw(l,(l+r)/2,lazy[v]),seg[v*2+1]=ustaw((l+r)/2+1,r,lazy[v]);
	lazy[v*2]=lazy[v],lazy[v*2+1]=lazy[v];
	lazy[v]=0;
}
void Insert(int pocz,int kon,int x,int p=0,int k=SS-1,int v=1){
	if(p>kon or k<pocz) return;
	if(p>=pocz and k<=kon) lazy[v]=x,seg[v]=ustaw(p,k,x);
	else{
		push(v,p,k);
		Insert(pocz,kon,x,p,(p+k)/2,v*2),Insert(pocz,kon,x,(p+k)/2+1,k,v*2+1);
		(seg[v]=seg[v*2]+seg[v*2+1]*pot[(k-p+1)/2])%=mod;
	}
}
bool hhash(string x){
	ll h=0;
	for(int i=x.size()-1;i>=0;i--) (h*=p)%=mod,(h+=int(x[i])-64)%=mod;
	if(m[h]) return 0;
	m[h]=1;
	v.push_back(x);
	return 1;
}
string cross(string a,string b){
	string res="";
	rep(i,a.size()){
		if(a[i]==b[i]) res+=a[i];
		else{
			if((a[i]=='J' and b[i]=='O') or (a[i]=='O' and b[i]=='J')) res+='I';
			if((a[i]=='I' and b[i]=='O') or (a[i]=='O' and b[i]=='I')) res+='J';
			if((a[i]=='J' and b[i]=='I') or (a[i]=='I' and b[i]=='J')) res+='O';
		}
	}
	return res;
}
void solve(){
	int n;
	cin>>n;
	string s1,s2,s3;
	cin>>s1>>s2>>s3;
	v.push_back(s1),v.push_back(s2),v.push_back(s3);
	ll pp=1;
	rep(i,n+10) pot[i]=pp,(sum[i]=(i==0?0:sum[i-1])+pp)%=mod,(pp*=p)%=mod;
	bool b=1;
	while(b){
		b=0;
		rep(i,v.size()){
			for(int j=i+1;j<v.size();j++){
				string xd=cross(v[i],v[j]);
				if(hhash(xd)) {b=1;break;}
			}
			if(b) break;
		}
	}
	int q;
	cin>>q;
	rep(i,n){
		char a;
		cin>>a;
		Insert(i,i,int(a)-64);
	}
	cout<<(m.count(seg[1])>0?"Yes":"No")<<"\n";
	for(int i=1;i<=q;i++){
		int a,b;
		char c;
		cin>>a>>b;
		a--,b--;
		cin>>c;
		Insert(a,b,int(c)-64);	
		cout<<(m.count(seg[1])>0?"Yes":"No")<<"\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); a++)
      |                                    ^
Main.cpp:45:2: note: in expansion of macro 'rep'
   45 |  rep(i,a.size()){
      |  ^~~
Main.cpp: In function 'void solve()':
Main.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); a++)
      |                                    ^
Main.cpp:66:3: note: in expansion of macro 'rep'
   66 |   rep(i,v.size()){
      |   ^~~
Main.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int j=i+1;j<v.size();j++){
      |                  ~^~~~~~~~~

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