Submission #1158629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158629		Der_Vlapos	Crossing (JOI21_crossing)	C++20	100 / 100	643 ms	29180 KiB

Main

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

#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back

#define int ll

int MOD7 = 1e9 + 7;
int MODFFT = 998244353;

struct segTree
{
	vector<pii> tree;
	vector<int> polynoms, pows;
	int sz = 0;

	void init(int n)
	{
		sz = 1;
		while (sz <= n)
			sz *= 2;
		polynoms.resize(sz);
		pows.resize(sz);
		tree.resize(2 * sz, {0, -1});

		int p = 1;
		for (int i = 0; i < sz; ++i)
		{
			pows[i] = p;
			polynoms[i] = ((i ? polynoms[i - 1] : 0) + p) % MODFFT;
			p = (MOD7 * p) % MODFFT;
		}
	}

	void upd(int v, int lv, int rv, int val)
	{
		tree[v].f = (polynoms[rv - lv - 1] * val) % MODFFT;
		tree[v].s = val;
	}

	void push(int v, int lv, int rv)
	{
		if (rv - lv == 1 or tree[v].s == -1)
			return;
		int m = (lv + rv) >> 1;
		upd(v * 2 + 1, lv, m, tree[v].s);
		upd(v * 2 + 2, m, rv, tree[v].s);
		tree[v].s = -1;
	}

	void set(int l, int r, int val, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (l <= lv and rv <= r)
		{
			upd(v, lv, rv, val);
			return;
		}
		if (rv <= l or r <= lv)
			return;
		int m = (lv + rv) >> 1;
		set(l, r, val, v * 2 + 1, lv, m);
		set(l, r, val, v * 2 + 2, m, rv);
		tree[v].f = (tree[v * 2 + 1].f * pows[m - lv] + tree[v * 2 + 2].f) % MODFFT;
	}

	void set(int l, int r, int val)
	{
		set(l, r, val, 0, 0, sz);
	}
};

struct test
{
	int n;
	map<pii, int> val;
	segTree myStr;

	vector<int> op(vector<int> &s1, vector<int> &s2)
	{
		vector<int> res(n);
		for (int i = 0; i < n; ++i)
			res[i] = val[{s1[i], s2[i]}];
		return res;
	}

	int getH(vector<int> &v)
	{
		int res = 0;
		for (int i = 0; i < myStr.sz; ++i)
		{
			res = (res * MOD7 + (i < n ? v[i] : 0)) % MODFFT;
		}
		return res;
	}

	void solve()
	{
		cin >> n;
		myStr.init(n);

		vector<vector<int>> strs(3, vector<int>(n));
		map<char, int> letter;
		letter['J'] = 0;
		letter['O'] = 1;
		letter['I'] = 2;
		map<int, bool> isInSet;
		for (int i = 0; i < 3; ++i)
		{
			for (int pos = 0; pos < n; ++pos)
			{
				char x;
				cin >> x;
				strs[i][pos] = letter[x];
			}
			isInSet[getH(strs[i])];
		}
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
			{
				val[{i, j}] = i;
				if (i != j)
					for (int k = 0; k < 3; ++k)
						if (k != i and k != j)
							val[{i, j}] = k;
			}

		for (int i = 0; i < strs.size(); ++i)
			for (int j = 0; j < i; ++j)
			{
				auto curs = op(strs[i], strs[j]);
				auto cur = getH(curs);

				if (isInSet.find(cur) == isInSet.end())
				{
					isInSet[cur] = 1;
					strs.pb(curs);
				}
			}

		int q;
		cin >> q;
		vector<int> HELP(n);
		for (int i = 0; i < n; ++i)
		{
			char x;
			cin >> x;
			myStr.set(i, i + 1, letter[x]);
			HELP[i] = letter[x];
		}
		cout << (isInSet.find(myStr.tree[0].f) != isInSet.end() ? "Yes" : "No") << "\n";

		for (int i = 0; i < q; ++i)
		{
			int l, r, x;
			cin >> l >> r;
			{
				char bf;
				cin >> bf;
				x = letter[bf];
			}
			--l;
			myStr.set(l, r, x);

			cout << (isInSet.find(myStr.tree[0].f) != isInSet.end() ? "Yes" : "No") << "\n";
		}
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

Main.cpp:175:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  175 | main()
      | ^~~~

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