Submission #765509

#	Time	Username	Problem	Language	Result	Execution time	Memory
765509		Drew_	Crossing (JOI21_crossing)	C++17	100 / 100	2013 ms	7632 KiB

Main

#include <iostream>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

#define ll long long

const int MAX = 2e5 + 69;
const int BLOCK = 777;
const int prime = 991;
const int mod = 1e9 + 9;

inline int add(ll x, ll y) { return (int)((x + y) % mod); }
inline int sub(ll x, ll y) { return (int)((x - y + mod) % mod); }
inline int mul(ll x, ll y) { return (int)((x * y) % mod); }
inline int fpow(ll x, ll y)
{
	int res = 1;
	while (y)
	{
		if (y & 1) res = mul(res, x);
		x = mul(x, x); y >>= 1;
	}
	return res;
}

int n, q;
int pwr[MAX], inv[MAX];
int ALLSAME[3]; //0: 'J', 1: 'O', 2: 'I', length: BLOCK
int value[MAX / BLOCK + 5]; //hash value for each block
char lazy[MAX / BLOCK + 5];

string s[3], t;
set<int> flower;

inline string combine(const string &a, const string &b)
{
	string res = "";
	for (int i = 0; i < n; ++i)
	{
		if (a[i] == b[i]) res += a[i];
		else if (a[i] != 'J' && b[i] != 'J') res += 'J';
		else if (a[i] != 'O' && b[i] != 'O') res += 'O';
		else if (a[i] != 'I' && b[i] != 'I') res += 'I';
	}
	if ((int)res.size() != n) cerr << a  << " " << b << '\n';
	return res;
}

inline void genFlower()
{
	set<string> st;
	for (int i = 0; i < 3; ++i)
		st.insert(s[i]);

	while (true)
	{
		bool ok = true;
		for (const string &a : st)
		{
			for (const string &b : st)
			{
				if (!st.count(combine(a, b)))
				{
					st.insert(combine(a, b));
					ok = false;
				}
			}
		}
		if (ok) break;
	}

	for (const string &x : st)
	{
		int sum = 0;
		for (int i = 0; i < n; ++i)
			sum = add(sum, mul(x[i], pwr[i]));
		flower.insert(sum);
	}
	return;
}

inline void update(int l, int r, char c)
{
	int id;
	if (c == 'J') id = 0;
	if (c == 'O') id = 1;
	if (c == 'I') id = 2;

	int b1 = l / BLOCK, b2 = r / BLOCK;
	if (b1 == b2)
	{
		if (lazy[b1])
		{
			for (int i = b1 * BLOCK; i < min(n, (b1 + 1) * BLOCK); ++i)
				t[i] = lazy[b1];
			lazy[b1] = 0;
		}
		for (int i = l; i <= r; ++i)
			t[i] = c;

		int sum = 0;
		for (int i = b1 * BLOCK; i < min(n, (b1 + 1) * BLOCK); ++i)
			sum = add(sum, mul(t[i], pwr[i - b1 * BLOCK]));
		value[b1] = sum;
	}
	else
	{
		update(l, (b1 + 1) * BLOCK - 1, c);
		update(b2 * BLOCK, r, c);
		for (int i = b1 + 1; i < b2; ++i)
			lazy[i] = c, value[i] = ALLSAME[id];
	}
}

inline void out()
{
	int sum = 0;
	for (int B = 0; B <= (n-1) / BLOCK; ++B)
		sum = add(sum, mul(value[B], pwr[B * BLOCK]));
	
	if (flower.count(sum)) cout << "Yes\n";
	else cout << "No\n";
}

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

	// The number of flower (after cross breeding) is small
	// Generate all Flower
	// Maintain current generation (string T)
	// using blocks, (size of sqrt(N))

	// Complexity: O(N + Q sqrt N)

	pwr[0] = 1;
	for (int i = 1; i < MAX; ++i)
		pwr[i] = mul(prime, pwr[i-1]);
	inv[MAX-1] = fpow(pwr[MAX-1], mod-2);
	for (int i = MAX-2; i >= 0; --i)
		inv[i] = mul(prime, inv[i+1]);

	for (int i = 0; i < 3; ++i)
	{
		int sum = 0;
		for (int j = 0; j < BLOCK; ++j)
			sum = add(sum, mul("JOI"[i], pwr[j]));
		ALLSAME[i] = sum;
	}

	cin >> n;
	for (int i = 0; i < 3; ++i)
		cin >> s[i];
	genFlower();

	cin >> q >> t;

	//generating value
	for (int B = 0; B <= (n-1) / BLOCK; ++B)
	{
		int sum = 0;
		for (int i = B * BLOCK; i < min(n, (B+1) * BLOCK); ++i)
			sum = add(sum, mul(t[i], pwr[i - B * BLOCK]));
		value[B] = sum;
	}

	out();
	while (q--)
	{
		int l, r;
		char c;
		cin >> l >> r >> c;

		update(l-1, r-1, c);
		out();
	}


	return 0;
}

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