Submission #422540

#	Time	Username	Problem	Language	Result	Execution time	Memory
422540		MetalPower	Crossing (JOI21_crossing)	C++14	100 / 100	542 ms	26176 KiB

Main

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

const int MX = 2e5 + 10;
const int MT = 5;
const int MOD[2] = {998244353, 420691273};

inline void chad(int& a, int b, int t){
	a = (a + b) % MOD[t];
}

inline int add(int a, int b, int t){
	return (a + b) % MOD[t];
}

inline int mul(int a, int b, int t){
	return 1ll * a * b % MOD[t];
}

inline int sub(int a, int b, int t){
	return (a + MOD[t] - b) % MOD[t];
}

int fp[MX][2], pref[MX][2];

void init(){
	pref[0][0] = pref[0][1] = fp[0][0] = fp[0][1] = 1;

	for(int i = 1; i < MX; i++){
		fp[i][0] = mul(fp[i - 1][0], MT, 0);
		fp[i][1] = mul(fp[i - 1][1], MT, 1);
		pref[i][0] = add(pref[i - 1][0], fp[i][0], 0);
		pref[i][1] = add(pref[i - 1][1], fp[i][1], 1);
	}
}

int sum(int l, int r, int t){
	return (l == 0) ? pref[r][t] : sub(pref[r][t], pref[l - 1][t], t);
}

int N, Q, arr[MX], hs[MX][9]; string s[3], T;
map<int, int> mp;

struct segtree{

	int st[MX * 4], lazy[MX * 4];

	void propagate(int idx, int l, int r){
		if(lazy[idx] != -1){
			st[idx] = mul(lazy[idx], sum(l, r, 0), 0);
			if(l != r){
				lazy[idx << 1] = lazy[idx << 1|1] = lazy[idx];
			}
			lazy[idx] = -1;
		}
	}

	void build(int idx, int l, int r){
		lazy[idx] = -1;

		if(l == r){
			st[idx] = mul(arr[l], fp[l][0], 0);
		}else{
			int mid = l + r >> 1;
			build(idx << 1, l, mid);
			build(idx << 1 | 1, mid + 1, r);
			st[idx] = add(st[idx << 1], st[idx << 1 | 1], 0);
		}
	}

	void upd(int idx, int l, int r, int from, int to, int val){
		propagate(idx, l, r);
		if(r < from || to < l) return;
		if(from <= l && r <= to){
			lazy[idx] = val;
			propagate(idx, l, r);
		}else{
			int mid = (l + r) >> 1;
			upd(idx << 1, l, mid, from, to, val);
			upd(idx << 1 | 1, mid + 1, r, from, to, val);
			st[idx] = add(st[idx << 1], st[idx << 1 | 1], 0);
		}
	}
} seg;

// Observation #1 : 
	// If you match J = 0, O = 1, I = 2
	// Crossing the strings is equal to 2(A[i] + B[i]) mod 3
	// Where A and B are the two strings

// Assume we have strings A, B, and C we can create strings
// 2A + 2B, 2A + 2C, 2B + 2C
// A + B + 2C, A + C + 2B, B + C + 2A

int main(){
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

	cin >> N >> s[0] >> s[1] >> s[2]; init();

	for(int j = 0; j < 3; j++){
		for(int i = 0; i < N; i++){
			if(s[j][i] == 'J') hs[i][j] = 0;
			else if(s[j][i] == 'O') hs[i][j] = 1;
			else if(s[j][i] == 'I') hs[i][j] = 2;
		}
	}

	for(int i = 0; i < N; i++){
		hs[i][3] = ((hs[i][0] + hs[i][1]) << 1) % 3;
	}

	for(int i = 0; i < N; i++){
		hs[i][4] = ((hs[i][0] + hs[i][2]) << 1) % 3;
	}

	for(int i = 0; i < N; i++){
		hs[i][5] = ((hs[i][1] + hs[i][2]) << 1) % 3;
	}

	for(int i = 0; i < N; i++){
		hs[i][6] = ((hs[i][2] + hs[i][3]) << 1) % 3;
	}

	for(int i = 0; i < N; i++){
		hs[i][7] = ((hs[i][1] + hs[i][4]) << 1) % 3;
	}

	for(int i = 0; i < N; i++){
		hs[i][8] = ((hs[i][0] + hs[i][5]) << 1) % 3;
	}

	for(int j = 0; j < 9; j++){
		int curr = 0;
		for(int i = 0; i < N; i++){
			chad(curr, mul(hs[i][j], fp[i][0], 0), 0);
		}
		mp[curr] = 1;
	}

	cin >> Q >> T;

	for(int i = 0; i < N; i++){
		if(T[i] == 'J') arr[i] = 0;
		else if(T[i] == 'O') arr[i] = 1;
		else if(T[i] == 'I') arr[i] = 2;
	}

	seg.build(1, 0, N - 1);
	cout << (mp[seg.st[1]] ? "Yes" : "No") << '\n';

	for(int i = 0; i < Q; i++){
		int l, r; char c; cin >> l >> r >> c; l--; r--;

		if(c == 'J') seg.upd(1, 0, N - 1, l, r, 0);
		else if(c == 'O') seg.upd(1, 0, N - 1, l, r, 1);
		else seg.upd(1, 0, N - 1, l, r, 2);

		cout << (mp[seg.st[1]] ? "Yes" : "No") << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(int, int, int)':
Main.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |    int mid = l + r >> 1;
      |              ~~^~~

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