Submission #670220

#	Time	Username	Problem	Language	Result	Execution time	Memory
670220		blue	Crossing (JOI21_crossing)	C++17	100 / 100	347 ms	38460 KiB

Main

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

using vi = vector<int>;
using ll = long long;

const ll mod = 1'000'000'007LL;

const int mx = 200'000;

ll pr[1 + mx];
ll basehash[3][1 + mx];



ll mul(ll a, ll b)
{
	return (a * b) % mod;
}

ll ad(ll a, ll b)
{
	return (a + b) % mod;
}


int N;
vi A, B, C;
vi AB, BC, CA;
vi ABC, BCA, CAB;

int op(int a, int b)
{
	if(a == b)
		return a;
	else
		return 0 + 1 + 2 - a - b;
}

vi op(vi a, vi b)
{
	vi res;
	for(int i = 0; i < N; i++)
		res.push_back(op(a[i], b[i]));
	return res;
}

vi stv(string s)
{
	vi res(N);
	for(int i = 0; i < N; i++)
	{
		if(s[i] == 'J')
			res[i] = 0;
		else if(s[i] == 'O')
			res[i] = 1;
		else
			res[i] = 2;
	}
	return res;
}

ll gethash(vi a)
{
	ll res = 0;
	for(int i = 0; i < N; i++)
		res = ad(res, mul(pr[i], a[i]));
	return res;
}





vi T;


struct segtree
{
	int l;
	int r;

	ll hashval;
	bool homo; //homogenous
	int typ;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree(int L, int R)
	{
		l = L;
		r = R;
		// cerr << "enter " << L << ' ' << R << '\n';
		if(L == R)
		{
			// cerr << "enter if\n";
			hashval = T[L];
			homo = 1;
			typ = T[L];
			// cerr << "check\n";
		}
		else
		{
			int m = (L + R) / 2;
			left = new segtree(L, m);
			right = new segtree(m+1, R);


			hashval = ad(left->hashval, mul(right->hashval, pr[left->r - left->l + 1]));
			homo = 0;
			typ = 0;
		}
		// cerr << "exit " << L << ' ' << R << " with hashval = " << hashval << '\n';
	}

	void update(int L, int R, int C)
	{
		if(R < l || r < L)
			return;
		else if(L <= l && r <= R)
		{
			hashval = basehash[C][r - l + 1];
			homo = 1;
			typ = C;
		}
		else
		{
			if(homo)
			{
				left->update(0, N-1, typ);
				right->update(0, N-1, typ);
			}

			left->update(L, R, C);
			right->update(L, R, C);

			hashval = ad(left->hashval, mul(right->hashval, pr[left->r - left->l + 1]));
			homo = 0;
			typ = 0;
		}

		// cerr << "after update hashval " << L << ' ' << R << " = " << hashval << '\n';
	}

};


// void out(vi a)
// {
// 	for(int u : a)
// 		cerr << u;
// 	cerr << '\n';
// }


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

	cin >> N;

	pr[0] = 1;
	pr[1] = 11;
	for(int i = 2; i <= N; i++)
		pr[i] = mul(pr[1], pr[i-1]);


	basehash[0][0] = basehash[1][0] = basehash[2][0] = 0;
	for(int i = 1; i <= N; i++)
	{
		for(int c = 0; c < 3; c++)
			basehash[c][i] = ad(basehash[c][i-1], mul(pr[i-1], c));
	}


	string a, b, c;
	cin >> a >> b >> c;

	A = stv(a);
	B = stv(b);
	C = stv(c);
	AB = op(A, B);
	BC = op(B, C);
	CA = op(C, A);
	ABC = op(A, BC);
	BCA = op(B, CA);
	CAB = op(C, AB);

	// cerr << A << ' ' << B << ' ' << C << ' ' << AB << ' ' << BC << ' ' << CA << '\n';// << ' ' << ABC << ' ' << BCA << ' ' << CAB << '\n';

	// out(A);
	// out(B);
	// out(C);
	// out(AB);
	// out(BC);
	// out(CA);
	// out(ABC);
	// out(BCA);
	// out(CAB);

	set<ll> goodhash;
	for(vi f : {A, B, C, AB, BC, CA, ABC, BCA, CAB})
	{
		// cerr << "inserting " << gethash(f) << '\n';
		goodhash.insert(gethash(f));
	}

	int Q;
	cin >> Q;

	string t0;
	cin >> t0;

	T = stv(t0);

	// out(T);

	// cerr << "start segtree\n";
	segtree S(0, N-1);
	// cerr << "end segtree\n";

	// cerr << "check hash : " << S.hashval << '\n';

	if(goodhash.find(S.hashval) != goodhash.end())
		cout << "Yes\n";
	else
		cout << "No\n";


	for(int q = 1; q <= Q; q++)
	{
		int L, R, C;
		char c;
		cin >> L >> R >> c;
		L--;
		R--;
		if(c == 'J')
			C = 0;
		else if(c == 'O')
			C = 1;
		else
			C = 2;

		S.update(L, R, C);

		if(goodhash.find(S.hashval) != goodhash.end())
		cout << "Yes\n";
		else
			cout << "No\n";
	}
}

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