Submission #683212

#	Time	Username	Problem	Language	Result	Execution time	Memory
683212		NK_	Crossing (JOI21_crossing)	C++17	100 / 100	502 ms	27536 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
using ll = long long;
using str = string;

const int MOD = 1e9 + 7;

struct Seg {
	const ll ID = 0; 
	vector<ll> pw, P;
	vector<ll> seg, lz, LX, RX; int N, B; ll cmb(int a, int b) {
		int len = RX[a] - LX[a] + 1;
		return (seg[a] + (pw[__lg(len)] * seg[b])) % MOD;
	};

	void init(int n, int b) {
		N = 1; while(N < n) N *= 2;
		B = b;
		seg.assign(2*N, ID), lz.assign(2*N, ID);
		LX.assign(2*N, -1), RX.assign(2*N, -1);

		pw = {B}; for(int i = 1; i <= __lg(N); i++) pw.push_back((pw.back() * 1LL * pw.back()) % MOD);
		P = {1}; for(int i = 1; i <= __lg(N); i++) P.push_back(((P.back() * pw[i - 1]) + P.back()) % MOD);

		build(1, 0, N-1);
	}

	void pull(int x) { seg[x] = cmb(2*x, 2*x+1); }

	void push(int x, int L, int R) {
		if (lz[x] == ID) return;
		seg[x] = (P[__lg(R-L+1)] * lz[x]) % MOD;
		// cerr << x << " " << L << " " << R << " => " << seg[x] << nl;
		if (L != R) for(int i = 0; i < 2; i++) lz[2*x+i] = lz[x];
		lz[x] = ID;
	}

	void build(int x, int L, int R) {
		LX[x] = L, RX[x] = R;
		if (L == R) return;
		int M = (L+R)/2; build(2*x, L, M);
		build(2*x+1, M+1, R);
	}

	void upd(int l, int r, int v, int x, int L, int R) {
		push(x, L, R); if (r < L || R < l) return;
		if (l <= L && R <= r) { lz[x] = v; push(x, L, R); return; }
		int M = (L+R)/2; upd(l, r, v, 2*x, L, M);
		upd(l, r, v, 2*x+1, M+1, R); pull(x);
	}

	ll get() { return seg[1]; }

	void upd(int l, int r, int v) { upd(l, r, v, 1, 0, N-1); }
};

const ll BASE = 1009;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	unordered_map<char, int> TO; TO['J'] = 1; TO['O'] = 2; TO['I'] = 3;

	
	int N; cin >> N;
	vector<str> A(3); for(auto &x : A) cin >> x;

	str R;
	auto comb = [&](const str &S, const str &T) {
		R = "";
		for(int i = 0; i < int(size(S)); i++) {
			if (S[i] == T[i]) R += S[i];
			else R += char('J' + 'O' + 'I' - S[i] - T[i]);
		}
		return R;
	};

	for(int _ = 0; _ < 2; _++) {
		vector<str> add; 
		for(int i = 0; i < int(size(A)); i++) for(int j = i+1; j < int(size(A)); j++) {
			add.push_back(comb(A[i], A[j]));
		}
		for(const auto &x : add) A.push_back(x);
		sort(begin(A), end(A));
		A.erase(unique(begin(A), end(A)), end(A));
	}
	
	vector<ll> HSH;
	auto HASH = [&](const str& S) {
		ll b = 1, H = 0;
		for(auto c : S) {
			H = (H + (b * TO[c])) % MOD;
			b = (b * BASE) % MOD;
		}
		return H;
	};

	for(const str& x : A) HSH.push_back(HASH(x));

	auto check = [&](const ll &x) -> bool {
		for(const auto &v : HSH) if (v == x) return 1;
		return 0;
	};

	Seg st; st.init(N, BASE);

	int Q; cin >> Q;
	str T; cin >> T;
	for(int i = 0; i < N; i++) st.upd(i, i, TO[T[i]]);
	
	cout << (check(st.get()) ? "Yes" : "No") << nl;
	for(int q = 0; q < Q; q++) {
		int l, r; char c; cin >> l >> r >> c; --l, --r;
		st.upd(l, r, TO[c]);
		cout << (check(st.get()) ? "Yes" : "No") << nl;
	}



    return 0;
}

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