Submission #422071

#	Time	Username	Problem	Language	Result	Execution time	Memory
422071		valerikk	Crossing (JOI21_crossing)	C++17	0 / 100	7091 ms	4036 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct Query {
	int l, r, c;
};

int get_id(char c) {
	if (c == 'J') return 0;
	if (c == 'O') return 1;
	if (c == 'I') return 2;
	assert(0);
	return -1;
}

vector<int> read(int n) {
	string s;
	cin >> s;
	vector<int> res(n);
	for (int i = 0; i < n; ++i) res[i] = get_id(s[i]);
	return res;
}

int n, q;
vector<vector<int>> strs;
vector<int> t;
vector<Query> queries;
vector<vector<int>> pref;
set<pair<pair<int, int>, int>> st;
int cnt_good;

vector<int> vec_add(vector<int> a, vector<int> b) {
	vector<int> res(n);
	for (int i = 0; i < n; ++i) res[i] = (6 + -a[i] - b[i]) % 3;
	return res;
}

bool check(int l, int r, int c) {
	return pref[r][c] - pref[l][c] == r - l;
}

void insert(int l, int r, int c) {
	st.insert({{l, r}, c});
	if (check(l, r, c)) ++cnt_good;
}

void erase(int l, int r, int c) {
	st.erase({{l, r}, c});
	if (check(l, r, c)) --cnt_good;
}

bool all_good() {
	return cnt_good == (int)st.size();
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < 3; ++i) strs.push_back(read(n));

	{
		bool was = 1;
		while (was) {
			/*for (auto s : strs) {
				for (auto c : s) cout << c;
				cout << endl;
			}*/
			was = 0;
			vector<vector<int>> added;
			for (auto s1 : strs) {
				for (auto s2 : strs) {
					auto cur = vec_add(s1, s2);
					bool has = 0;
					for (auto s : strs) has |= cur == s;
					if (!has) {
						added.push_back(cur);
						was = 1;
					}
				}
			}
			for (auto s : added) strs.push_back(s);
		}
	}

	cin >> q;
	t = read(n);
	queries.resize(q);
	for (int i = 0; i < q; ++i) {
		cin >> queries[i].l >> queries[i].r;
		--queries[i].l;
		char c;
		cin >> c;
		queries[i].c = get_id(c);
	}
	vector<int> ans(q + 1, 0);

	for (auto s : strs) {
		pref.assign(n + 1, vector<int>(3, 0));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < 3; ++j) pref[i + 1][j] = pref[i][j] + (s[i] == j);
		}
		st = {};
		cnt_good = 0;
		for (int i = 0; i < n; ++i) insert(i, i + 1, t[i]);
		for (int i = 0; i <= q; ++i) {
			ans[i] |= all_good();
			if (i != q) {
				int l = queries[i].l, r = queries[i].r, c = queries[i].c;
				vector<pair<pair<int, int>, int>> inserted, erased;
				auto it = st.lower_bound({{l, -1}, -1});
				if (it != st.begin()) --it;
				for (int iteration = 0; it != st.end(); ++iteration, ++it) {
					int curl = it->first.first, curr = it->first.second, curc = it->second;
					if (iteration != 0 && (curl >= r || curr <= l)) break;
					if (curl >= r || curr <= l) continue;
					int cl = max(curl, l), cr = min(curr, r);
					erased.push_back({{curl, curr}, curc});
					inserted.push_back({{cl, cr}, c});
					inserted.push_back({{curl, cl}, curc});
					inserted.push_back({{curr, cr}, curc});
				}
				for (auto seg : erased) erase(seg.first.first, seg.first.second, seg.second);
				for (auto seg : inserted) {
					if (seg.first.first < seg.first.second) insert(seg.first.first, seg.first.second, seg.second);
				}
			}
		}
	}

	for (int i = 0; i <= q; ++i) cout << (ans[i] ? "Yes\n" : "No\n");
	return 0;
}

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