Submission #1255496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255496		arashmemar	Crossing (JOI21_crossing)	C++20	100 / 100	3932 ms	87388 KiB

Main

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

const int maxn = 2e5 + 100, p = 701, mod = 1e9 + 7;

int ptp[maxn];

int n;

int ch(char a)
{
	if (a == 'J')
	{
		return 0;
	}
	if (a == 'O')
	{
		return 1;
	}
	return 2;
}

char f(char a, char b)
{
	if (a == b)
	{
		return b;
	}
	set <char> tmp = {'J', 'O', 'I'};
	tmp.erase(a);
	tmp.erase(b);
	return *tmp.begin();
}

string x(string s1, string s2)
{
	string ans;
	for (int i = 0;i < n;i++)
	{
		ans.push_back(f(s1[i], s2[i]));
	}
	return ans;
}

int h(string s)
{
	long long int ret = 0;
	for (int i = 0;i < n;i++)
	{
		ret += (long long int)ptp[i] * s[i] % mod;
	}
	return ret % mod;
}

set <int> pos;
vector <string> ss;

void add(string s)
{
	if (pos.find(h(s)) != pos.end())
	{
		return ;
	}
	vector <string> tmp;
	for (auto o : ss)
	{
		int tmpe;
		if (pos.find(tmpe = h(x(s, o))) == pos.end())
		{
			tmp.push_back(x(s, o));
		}
	}
	pos.insert(h(s));
	ss.push_back(s);
	for (auto o : tmp)
	{
		add(o);
	}
	return ;
}

bool ok[9][4 * maxn];
int noe[9][4 * maxn][3], lazy[9][4 * maxn];

void init(int id, int L, int R, int t)
{
	lazy[t][id] = -1;
	if (R - L == 1)
	{
		noe[t][id][ch(ss[t][L - 1])] = 1;
		return ;
	}
	int mid = (L + R) / 2;
	init(id * 2 + 0, L, mid, t);
	init(id * 2 + 1, mid, R, t);
	for (int i = 0;i < 3;i++)
	{
		noe[t][id][i] = noe[t][id * 2 + 0][i] + noe[t][id * 2 + 1][i];
	}
	return ;
}

void spread(int id, int L, int R, int t)
{
	if (lazy[t][id] == -1)
	{
		return ;
	}
	ok[t][id] = (noe[t][id][lazy[t][id]] == R - L);
	if (R - L - 1)
	{
		lazy[t][id * 2 + 0] = lazy[t][id];
		lazy[t][id * 2 + 1] = lazy[t][id];
	}
	lazy[t][id] = -1;
	return ;
}

void update(int id, int L, int R, int l, int r, int v, int t)
{
	spread(id, L, R, t);
	if (L == l and R == r)
	{
		lazy[t][id] = v;
		spread(id, L, R, t);
		return ;
	}
	int mid = (L + R) / 2;
	if (l < mid)
	{
		update(id * 2 + 0, L, mid, l, min(r, mid), v, t);
	}
	if (r > mid)
	{
		update(id * 2 + 1, mid, R, max(l, mid), r, v, t);
	}
	spread(id * 2 + 0, L, mid, t);
	spread(id * 2 + 1, mid, R, t);
	for (int i = 0;i < 3;i++)
	{
		noe[t][id][i] = noe[t][id * 2 + 0][i] + noe[t][id * 2 + 1][i];
	}
	ok[t][id] = (ok[t][id * 2 + 0] & ok[t][id * 2 + 1]); return ;
}

string get()
{
	bool ans = 0;
	for (int i = 0;i < ss.size();i++)
	{
		ans |= ok[i][1];
	}
	if (ans)
	{
		return "Yes";
	}
	return "No";
}

int main()
{
	ptp[0] = 1;
	for (int i = 1;i < maxn;i++)
	{
		ptp[i] = (long long int)ptp[i - 1] * p % mod;
	}
	cin >> n;
	for (int i = 1;i <= 3;i++)
	{
		string s;
		cin >> s;
		add(s);
	}

	for (int i = 0;i < ss.size();i++)
	{
		init(1, 1, n + 1, i);
	}

	int q;
	cin >> q;
	string s;
	cin >> s;
	for (int i = 0;i < n;i++)
	{
		for (int t = 0;t < ss.size();t++)
		{
			update(1, 1, n + 1, i + 1, i + 2, ch(s[i]), t);
		}
	}
	cout << get() << '\n';
	while (q--)
	{
		int l, r;
		char y;
		cin >> l >> r >> y;
		for (int t = 0;t < ss.size();t++)
		{
			update(1, 1, n + 1, l, r + 1, ch(y), t);
		}
		cout << get() << '\n';
	}

}

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