Submission #888449

#	Time	Username	Problem	Language	Result	Execution time	Memory
888449		Hakiers	Crossing (JOI21_crossing)	C++17	100 / 100	340 ms	40160 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 2e5 + 7;
constexpr int BASE = 1 << 18;
constexpr ll mod = 1e9 + 7;
constexpr ll P = 7;
map<ll, bool> mapa;
int GENE[MAXN][3];
int gen[MAXN][9];
int wzorzec[MAXN];
ll TREE[BASE << 1];
ll LAZY[BASE << 1];
ll pot[BASE];
ll sumpot[BASE];
int n, q;

void generate(){
	// -(A+B)
	for(int i = 1; i <= n; i++)
		gen[i][0] = (-(GENE[i][0] + GENE[i][1]) + 6)%3;
	// -(A+C)
	for(int i = 1; i <= n; i++)
		gen[i][1] = (-(GENE[i][0] + GENE[i][2]) + 6)%3;
	// -(B+C)
	for(int i = 1; i <= n; i++)
		gen[i][2] = (-(GENE[i][1] + GENE[i][2]) + 6)%3;	
	// (A+B-C)
	for(int i = 1; i <= n; i++)
		gen[i][3] = ((GENE[i][0] + GENE[i][1] - GENE[i][2]) + 6)%3;	
	// (A-B+C)
	for(int i = 1; i <= n; i++)
		gen[i][4] = ((GENE[i][0] - GENE[i][1] + GENE[i][2]) + 6)%3;
	//(-A+B+C)
	for(int i = 1; i <= n; i++)
		gen[i][5] = ((-GENE[i][0] + GENE[i][1] + GENE[i][2]) + 6)%3;
	//default
	for(int i = 1; i <= n; i++){
		gen[i][6] = GENE[i][0];
		gen[i][7] = GENE[i][1];
		gen[i][8] = GENE[i][2];
	}	
}

void compute(){
	pot[0] = 1;
	sumpot[0] = pot[0];
	for(int i = 1; i <= n; i++){
		pot[i] = (P*pot[i-1])%mod;
		sumpot[i] = (pot[i] + sumpot[i-1])%mod;
	}
}

void makehash(int v){
	ll act = 0;
	for(int i = 1; i <= n; i++)
		act = (act + (gen[i][v]*pot[i])%mod)%mod;

	mapa[act] = 1;
}

ll sum(int a, int b){
	ll out = (sumpot[b] - sumpot[a-1])%mod;
	
	while(out < 0)
		out += mod;
	
	return out;
}

void push(int v, int l, int r, int a, int b, int mid){
	if(LAZY[v] >= 0){
		LAZY[l] = LAZY[v];
		LAZY[r] = LAZY[v];
		
		TREE[l] = (LAZY[v]*sum(a, mid))%mod;
		TREE[r] = (LAZY[v]*sum(mid+1, b))%mod;
	}
	LAZY[v] = -1;
}

void update(int v, int a, int b, int l, int r, ll x){
	if(b < l || r < a) return;
	else if(l <= a && b <= r){
		TREE[v] = (x*sum(a, b))%mod;
		LAZY[v] = x;
	}
	else{
		int mid = (a+b)/2;
		push(v, 2*v, 2*v+1, a, b, mid);
		update(2*v, a, mid, l, r, x);
		update(2*v+1, mid+1, b, l, r, x);
		
		TREE[v] = (TREE[2*v] + TREE[2*v+1])%mod;
	}
}

bool check(){
	return mapa[(TREE[1]%mod)];
}

void treeinit(){
	for(int i = 0; i <(BASE<<1); i++)
		LAZY[i] = -1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	string str;
	for(int i = 0; i <= 2; i++){
		cin >> str;
		
		for(int j = 0; j < n; j++){
			int a;
			if(str[j] == 'J') a = 0;
			else if(str[j] == 'O') a = 1;
			else a = 2;
			GENE[j+1][i] = a;
		}
	}
	generate();
	compute();
	treeinit();
	for(int i = 0; i < 9; i++)
		makehash(i);
		
	cin >> q;
	cin >> str;
	for(int i = 1; i <= n; i++){
		int a;
		if(str[i-1] == 'J') a = 0;
		else if(str[i-1] == 'O') a = 1;
		else a = 2;
		wzorzec[i] = a;
		update(1, 0, BASE-1, i, i, a);
	}
	
	if(check()) cout << "Yes \n";
	else cout << "No \n";
	
	while(q--){
		int a, b;
		char c;
		cin >> a >> b >> c;
		ll x;
		if(c == 'J') x = 0;
		else if(c == 'O') x = 1;
		else x = 2;
		update(1, 0, BASE-1, a, b, x);
		
		if(check()) cout << "Yes \n";
		else cout << "No \n";
	}

}

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