제출 #420056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420056		errorgorn	Crossing (JOI21_crossing)	C++17	100 / 100	588 ms	33364 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

const int MOD=1000000007;
const int P=177013;
ll powp[200005];

mt19937 rng(177013);

#define i3 tuple<int,int,int>

i3 conv(i3 i,i3 j){
	int ia,ib,ic;
	int ja,jb,jc;
	
	tie(ia,ib,ic)=i;
	tie(ja,jb,jc)=j;
	
	return {
		(6-ia-ja)%3,
		(6-ib-jb)%3,
		(6-ic-jc)%3
	};
}

set<i3> s[10];

int n,q;
string st[3];
ll v[3][200005];

map<char,int> id;
ll hh[3];
set<int> good;

string qu;

struct node{
	int s,e,m;
	ll val=0,lazy=-1;
	ll mul=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		rep(x,s,e+1) mul=(mul+powp[x])%MOD;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy!=-1){
			val=hh[lazy]*mul%MOD;
			
			if (s!=e){
				l->lazy=lazy;
				r->lazy=lazy;
			}
			lazy=-1;
		}
	}
	
	void update(int i,int j,int k){
		propo();
		if (s==i && e==j) lazy=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=(l->val+r->val)%MOD;
		}
	}
} *root;

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	powp[0]=1;
	rep(x,1,200005) powp[x]=powp[x-1]*P%MOD;
	
	id['J']=0;
	id['O']=1;
	id['I']=2;
	
	rep(x,0,3) hh[x]=rng()%MOD;
	//rep(x,0,3) hh[x]=x+1;
	
	s[0].insert({1,0,0}),s[0].insert({0,1,0}),s[0].insert({0,0,1});
	
	rep(x,0,9){
		s[x+1]=s[x];
		for (auto &it:s[x]) for (auto &it2:s[x]){
			s[x+1].insert(conv(it,it2));
		}
	}
	
	cin>>n;
	rep(x,0,3) cin>>st[x];
	rep(x,0,3) rep(y,0,n){
		v[x][y]=id[st[x][y]];
	}
	
	for (auto &it:s[9]){
		ll arr[3];
		tie(arr[0],arr[1],arr[2])=it;
		
		ll curr=0;
		
		rep(x,0,n){
			ll base=0;
			rep(y,0,3) base=(base+v[y][x]*arr[y])%3;
			
			curr=(curr+hh[base]*powp[x])%MOD;
			
			//cout<<base<<" ";
		}
		//cout<<endl;
		
		good.insert(curr);
		//cout<<curr<<endl;
	}
	
	cin>>q;
	cin>>qu;
	
	root=new node(0,200005);
	rep(x,0,n) root->update(x,x,id[qu[x]]);
	//rep(x,0,n) cout<<id[qu[x]]<<" "; cout<<endl;
	//cout<<root->val<<endl;
	
	if (good.count(root->val)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	int a,b;
	char c;
	
	while (q--){
		cin>>a>>b>>c;
		root->update(a-1,b-1,id[c]);
		
		if (good.count(root->val)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

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

Main.cpp: In constructor 'node::node(int, int)':
Main.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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