Submission #419885

#	Time	Username	Problem	Language	Result	Execution time	Memory
419885		Berted	Crossing (JOI21_crossing)	C++14	100 / 100	609 ms	24676 KiB

Main

#include <iostream>
#include <set>
#include <vector>
#define ll long long

using namespace std;

const int Hs = 2, SZ = (1 << 19) + 5;

const char cmp[3] = {'J', 'O', 'I'};
const ll MD[Hs] = {1000000007, 420691273}, Hp[Hs] = {17, 7};
ll pre[Hs][2][200001];

inline int getVal(const char &c)
{
	if (c == 'J') return 1;
	else if (c == 'O') return 2;
	else if (c == 'I') return 3;
	else return -1;
}

struct Hash
{
	int sz = 0; ll A[Hs] = {};
	inline void build(const string &s, const int &l, const int &r)
	{
		sz = r - l + 1;
		for (int i = l; i <= r; i++)
		{
			for (int j = 0; j < Hs; j++) {A[j] = (A[j] * Hp[j] % MD[j] + getVal(s[i])) % MD[j];}
		}
	}
};

inline Hash merge(const Hash &l, const Hash &r)
{
	Hash ret;
	for (int i = 0; i < Hs; i++)
	{
		ret.A[i] = (r.A[i] + l.A[i] * pre[i][0][r.sz]) % MD[i];
		ret.sz = l.sz + r.sz;
	}
	return ret;
}

inline bool operator==(const Hash &l, const Hash &r)
{
	for (int i = 0; i < Hs; i++)
	{
		if (l.A[i] != r.A[i]) return 0;
	}
	return 1;
}

int N, Q;
string A, B, C, T;
set<string> S;
Hash seg[SZ]; int lz[SZ];

void prop(int idx, int L, int R)
{
	if (L <= R)
	{
		if (lz[idx])
		{
			for (int i = 0; i < Hs; i++) {seg[idx].A[i] = pre[i][1][R - L + 1] * lz[idx] % MD[i];}
			if (L < R)
			{
				lz[2 * idx] = lz[idx];
				lz[2 * idx + 1] = lz[idx];
			}
			lz[idx] = 0;
		}
	}
}

void build(int idx, int L, int R, const string &T)
{
	//cerr << "BLD: " << L << " " << R << "\n";
	if (L < R)
	{
		int M = L + R >> 1;
		build(2 * idx, L, M, T);
		build(2 * idx + 1, M + 1, R, T);
		seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
	}
	else if (L == R) {seg[idx].build(T, L, R);}
}

inline void upd(int idx, int L, int R, int l, int r, int t)
{
	l = max(L, l); r = min(R, r);
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) {lz[idx] = t; prop(idx, L, R);}
		else
		{
			int M = L + R >> 1;
			upd(2 * idx, L, M, l, r, t);
			upd(2 * idx + 1, M + 1, R, l, r, t);
			seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

inline string cross(const string &A, const string &B)
{
	string ret;
	for (int i = 0; i < N; i++)
	{
		int a = getVal(A[i]) - 1, b = getVal(B[i]) - 1;
		if (a == b) ret.push_back(cmp[a]);
		else ret.push_back(cmp[3 - a - b]);
	}
	return ret;
}

vector<Hash> dat;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	cin >> A >> B >> C;

	for (int i = 0; i < Hs; i++)		// Hashing precomputation.
	{
		pre[i][0][0] = 1;
		for (int k = 1; k <= N; k++)
		{
			pre[i][0][k] = pre[i][0][k - 1] * Hp[i] % MD[i];
			pre[i][1][k] = (pre[i][1][k - 1] * Hp[i] % MD[i] + 1) % MD[i];
		}
	}

	S.insert(A); S.insert(B); S.insert(C);
	for (const auto &x : S)
		for (const auto &y : S) S.insert(cross(x, y));

	for (const auto &x : S) 
	{
		dat.push_back(Hash());
		dat.back().build(x, 0, N - 1);
		//cerr << x << "\n" << dat.back().A[0] << "\n" << dat.back().A[1] << "\n";
	}

	cin >> Q;
	cin >> T;

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

	for (int i = 0; i <= Q; i++)
	{
		bool found = 0;
		for (const auto &x : dat)
		{
			if (x == seg[1]) {found = 1; break;} 
		}
		if (found) cout << "Yes\n";
		else cout << "No\n";
		if (i < Q)
		{
			int l, r; char c; cin >> l >> r >> c;
			upd(1, 0, N - 1, l - 1, r - 1, getVal(c));
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int, const string&)':
Main.cpp:82:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int M = L + R >> 1;
      |           ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:99:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |    int M = L + R >> 1;
      |            ~~^~~

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