Submission #531956

#	Time	Username	Problem	Language	Result	Execution time	Memory
531956		Tw_28e7	Crossing (JOI21_crossing)	C++17	0 / 100	75 ms	4048 KiB

Main

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace std;
using namespace __gnu_pbds;
#define LL long long
#define pLL pair<long long, long long>
#define F first
#define S second
#define pb push_back
#define rz resize
#define all(x) x.begin(), x.end()
#define endl '\n'

void Star_Brust_Stream()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}
const LL INF = 1e18, MOD = 1e9 + 7;
vector<LL> meee, pre;
vector<LL> tar;
struct seg
{
	LL l, r, v, m, lz;
	seg *ln, *rn;
	seg(LL ll, LL rr) : l(ll), r(rr)
	{
		lz = -1;
		m = (l + r) >> 1;
		if (l != r - 1)
		{

			ln = new seg(l, m);
			rn = new seg(m, r);
			v = comb(ln->v, rn->v);
		}
		else
		{
			v = tar[l];
		}
		return;
	}
	LL comb(LL a, LL b)
	{
		return (((b * meee[r - m]) % MOD) + a) % MOD;
	}
	LL rv()
	{
		if (lz == -1)
		{
			return v;
		}
		return (lz * pre[(r - l - 1)]) % MOD;
	}

	void push()
	{
		if (lz != -1)
		{
			ln->lz = lz;
			rn->lz = lz;
			v = rv();
			lz = -1;
		}
	}
	LL ask(LL ll, LL rr)
	{
		if (l == ll && r == rr)
		{
			return rv() % MOD;
		}
		push();
		if (m >= rr)
		{
			return ln->ask(ll, rr) % MOD;
		}
		else if (m <= ll)
		{
			return rn->ask(ll, rr) % MOD;
		}
		else
		{
			return comb(ln->ask(ll, m), rn->ask(m, rr));
		}
	}
	void revise(LL ll, LL rr, LL num)
	{
		if (l == ll && r == rr)
		{
			lz = num;
			return;
		}
		else
		{
			push();
			LL m = (l + r) >> 1;
			if (m >= rr)
			{
				ln->revise(ll, rr, num);
			}
			else if (m <= ll)
			{
				rn->revise(ll, rr, num);
			}
			else
			{
				ln->revise(ll, m, num);
				rn->revise(m, rr, num);
			}
			v = comb(ln->rv(), rn->rv());
		}
	}
};
int main()
{
	Star_Brust_Stream();
	meee.rz(2e5 + 10);
	pre.rz(2e5 + 10);
	meee[0] = 1;
	pre[0] = 1;
	for (int i = 1; i < meee.size(); i++)
	{
		meee[i] = (meee[i - 1] * 37) % MOD;
		pre[i] = (pre[i - 1] + meee[i]) % MOD;
	}
	set<string> ne;
	set<LL> s;
	LL n;
	cin >> n;
	vector<string> vs(3);
	for (int i = 0; i < 3; i++)
	{
		cin >> vs[i];
		ne.insert(vs[i]);
	}

	for (int i = 0; i < 3; i++)
	{
		LL h = 0;
		for (int j = 0; j < n; j++)
		{
			h = (h * 37) % MOD;
			h = (h + vs[i][j]) % MOD;
		}
		s.insert(h);
	}
	LL x[3] = {0, 1, 2};
	LL y[3] = {1, 2, 0};

	for (int i = 0; i < 3; i++)
	{
		string re;
		for (int j = 0; j < n; j++)
		{
			if (vs[x[i]][j] == vs[y[i]][j])
			{
				re += vs[x[i]][j];
			}
			else
			{
				set<char> c;
				c.insert('J');
				c.insert('O');
				c.insert('I');
				c.erase(vs[x[i]][j]);
				c.erase(vs[y[i]][j]);
				re += *c.begin();
			}
		}
		LL h = 0;
		for (int j = 0; j < n; j++)
		{
			h = (h * 37) % MOD;
			h = (h + re[j]) % MOD;
		}

		ne.insert(re);
		s.insert(h);
	}
	for (string str : ne)
	{
		string re;
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (str[j] == vs[i][j])
				{
					re += vs[i][j];
				}
				else
				{
					set<char> c;
					c.insert('J');
					c.insert('O');
					c.insert('I');
					c.erase(vs[i][j]);
					c.erase(str[j]);
					re += *c.begin();
				}
			}
			LL h = 0;
			for (int j = 0; j < n; j++)
			{
				h = (h * 37) % MOD;
				h = (h + re[j]) % MOD;
			}

			s.insert(h);
		}
	}
	LL q;
	cin >> q;
	string t;
	cin >> t;
	tar.rz(n);
	for (int i = 0; i < n; i++)
	{
		tar[i] = t[i];
	}

	seg st(0, n);

	if (s.count(st.rv()))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	while (q--)
	{
		LL a, b;
		char c;
		cin >> a >> b >> c;
		a--;
		st.revise(a, b, c);

		if (s.count(st.rv()))
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}

	//	system("pause");
	return 0;
}
/*
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for (int i = 1; i < meee.size(); i++)
      |                  ~~^~~~~~~~~~~~~

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