제출 #419651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419651		alishahali1382	Crossing (JOI21_crossing)	C++14	100 / 100	1857 ms	47568 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef pair<pii, int> piii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())

const int inf=1000010000;
const int mod=1000000007;
const int MAXN=300010, TED=5;

int to_int(char ch){
	if (ch=='J') return 0;
	if (ch=='O') return 1;
	return 2;
}

int n, m, q, k, u, v, x, y, t, l, r, ans;
int A[3][MAXN], B[9][MAXN], T0[MAXN];
int Z[27];
char ch;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Solver{
	ll rnd[MAXN], ps[MAXN];
	int Bs[9];
	int seg[MAXN<<2], lazy[MAXN<<2];
	void Start(){
		for (int i=1; i<=n; i++){
			rnd[i]=rng()%mod;
			ps[i]=ps[i-1]+rnd[i];
		}
		for (int j=0; j<9; j++){
			ll sum=0;
			for (int i=1; i<=n; i++) sum+=rnd[i]*B[j][i];
			Bs[j]=sum%mod;
		}
		Build(1, 1, n+1);
	}
	int Build(int id, int tl, int tr){
		lazy[id]=-1;
		if (tr-tl==1) return seg[id]=rnd[tl]*T0[tl]%mod;
		int mid=(tl+tr)>>1;
		return seg[id]=(Build(id<<1, tl, mid)+Build(id<<1 | 1, mid, tr))%mod;
	}
	inline void add_lazy(int id, int tl, int tr, int val){
		// cerr<<"lazy "<<tl<<" "<<tr<<"  "<<val<<"\n";
		lazy[id]=val;
		seg[id]=(ps[tr-1]-ps[tl-1])*val%mod;
	}
	inline void shift(int id, int tl, int tr){
		if (lazy[id]!=-1){
			int mid=(tl+tr)>>1;
			add_lazy(id<<1, tl, mid, lazy[id]);
			add_lazy(id<<1 | 1, mid, tr, lazy[id]);
			lazy[id]=-1;
		}
	}
	void Set(int id, int tl, int tr, int l, int r, int val){
		if (r<=tl || tr<=l) return ;
		if (l<=tl && tr<=r){
			// cerr<<"add_lazy "<<tl<<" "<<tr<<"  "<<val<<"\n";
			add_lazy(id, tl, tr, val);
			return ;
		}
		shift(id, tl, tr);
		int mid=(tl+tr)>>1;
		Set(id<<1, tl, mid, l, r, val);
		Set(id<<1 | 1, mid, tr, l, r, val);
		seg[id]=(seg[id<<1] + seg[id<<1 | 1])%mod;
	}
	bool Solve(){
		for (int i=0; i<9; i++) if (Bs[i]==seg[1]) return 1;
		return 0;
	}
} solver[TED];

bool Solve(){
	for (int i=0; i<TED; i++) if (!solver[i].Solve()) return 0;
	return 1;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	Z[1]=Z[3]=Z[9]=1;
	for (int i=0; i<27; i++){
		for (int x=0; x<27; x++) for (int y=0; y<27; y++) if (Z[x] && Z[y]){
			int a=2*((x/1%3)+(y/1%3))%3;
			int b=2*((x/3%3)+(y/3%3))%3;
			int c=2*((x/9%3)+(y/9%3))%3;
			Z[a+3*b+9*c]=1;
		}
	}
	// for (int i=0; i<27; i++) if (Z[i]) cerr<<i%3<<" "<<i/3%3<<" "<<i/9%3<<"\n";
	cin>>n;
	for (int i=0; i<3; i++){
		for (int j=1; j<=n; j++){
			cin>>ch;
			A[i][j]=to_int(ch);
		}
	}
	for (int z=0; z<27; z++) if (Z[z]){
		int a=(z/1%3), b=(z/3%3), c=(z/9%3);
		for (int i=1; i<=n; i++)
			B[t][i]=(A[0][i]*a + A[1][i]*b + A[2][i]*c)%3;
		t++;
	}
	assert(t==9);
	
	cin>>m;
	for (int i=1; i<=n; i++){
		cin>>ch;
		T0[i]=to_int(ch);
	}
	
	for (int i=0; i<TED; i++) solver[i].Start();
	cout<<(Solve()?"Yes":"No")<<"\n";
	while (m--){
		cin>>l>>r>>ch;
		r++;
		for (int i=0; i<TED; i++) solver[i].Set(1, 1, n+1, l, r, to_int(ch));
		cout<<(Solve()?"Yes":"No")<<"\n";
		// debug(solver.seg[1])
	}

	return 0;
}
/*
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

*/

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