Submission #871873

#	Time	Username	Problem	Language	Result	Execution time	Memory
871873		serifefedartar	Crossing (JOI21_crossing)	C++17	49 / 100	299 ms	27492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 2e5 + 100;

const ll P = 31;
ll powP[2*MAXN];
ll inv;
struct Node {
	ll len, hash;
	Node() { }
	Node(ll _len, ll _hash) : len(_len), hash(_hash) { }
};

Node merge(Node A, Node B) {
	Node new_node;
	new_node.hash = (A.hash * powP[B.len] + B.hash) % MOD;
	new_node.len = A.len + B.len;
	return new_node;
}

set<ll> hashes;
vector<int> new_seq;
vector<int> cross(vector<int> A, vector<int> B) {
	int n = A.size();
	vector<int> q;
	for (int i = 0; i < n; i++)
		q.push_back((2 * (A[i] + B[i])) % 3);
	return q;
}

Node sg[4*MAXN];
ll lazy[4*MAXN];
ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 2) 
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

void push(int k, int a, int b) {
	if (lazy[k] != -1) {
		int l = sg[k].len;
		sg[k].hash = (lazy[k] * (((powP[l] - 1) * inv) % MOD)) % MOD;
		if (a != b) {
			lazy[2*k] = lazy[k];
			lazy[2*k+1] = lazy[k];
		}
		lazy[k] = -1;
	}
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k].len = 1;
		sg[k].hash = new_seq[a-1] + 1;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
	push(k, a, b);
	if (b < q_l || a > q_r)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] = val;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, val);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

int main() {
	fast
	inv = expo(P-1, MOD-2);
	powP[0] = 1;
	for (int i = 1; i < 2*MAXN; i++)
		powP[i] = (powP[i-1] * P) % MOD;
	memset(lazy, -1, sizeof(lazy));
	int N;
	cin >> N;

	vector<int> s[3];
	for (int seq = 0; seq < 3; seq++)
		for (int i = 0; i < N; i++) {
		char ch;
		cin >> ch;
		s[seq].push_back(ch == 'J' ? 0 : (ch == 'O' ? 1 : 2));
	}

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (i == j && j == k)
					continue;
				vector<int> c = cross(s[i], s[j]);
				c = cross(c, s[k]);

				ll hash = 0;
				for (int i = 0; i < N; i++)
					hash = (hash * P + (c[i] + 1)) % MOD;
				hashes.insert(hash);
			}
		}
	}

	int q;
	cin >> q;
	for (int i = 0; i < N; i++) {
		char ch;
		cin >> ch;
		new_seq.push_back(ch == 'J' ? 0 : (ch == 'O' ? 1 : 2));
	}
	init(1, 1, N);
	push(1, 1, N);

	if (hashes.count(sg[1].hash))
		cout << "Yes\n";
	else
		cout << "No\n";

	while (q--) {
		int l, r, val; char ch;
		cin >> l >> r >> ch;
		val = ch == 'J' ? 0 : (ch == 'O' ? 1 : 2);
		update(1, 1, N, l, r, val + 1);

		push(1, 1, N);
		if (hashes.count(sg[1].hash))
			cout << "Yes\n";
		else
			cout << "No\n";
	}
}

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