Submission #422090

#	Time	Username	Problem	Language	Result	Execution time	Memory
422090		valerikk	Crossing (JOI21_crossing)	C++17	0 / 100	7016 ms	3996 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;
const vector<vector<int>> coefs = {{0, 0, 1},
                                   {0, 1, 0},
                                   {1, 0, 0},
                                   {0, 2, 2},
                                   {2, 0, 2},
                                   {0, 2, 2},
                                   {2, 2, 0},
                                   {2, 0, 2},
                                   {2, 2, 0},
                                   {1, 1, 2},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {1, 2, 1},
                                   {2, 1, 1},
                                   {2, 1, 1},
                                   {2, 1, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {1, 2, 1},
                                   {1, 1, 2},
                                   {1, 1, 2},
                                   {2, 1, 1},
                                   {2, 1, 1},
                                   {2, 1, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {2, 1, 1},
                                   {1, 2, 1},
                                   {2, 1, 1},
                                   {1, 2, 1},
                                   {1, 1, 2},
                                   {1, 1, 2},
                                   {2, 1, 1},
                                   {2, 1, 1},
                                   {1, 1, 2},
                                   {1, 2, 1},
                                   {2, 1, 1},
                                   {1, 2, 1},
                                   {2, 1, 1}};

vector<int> str_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;
}

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));

	{
		vector<vector<int>> nstrs;
		for (auto v : coefs) {
			vector<int> cur(n);
			for (int i = 0; i < n; ++i) cur[i] = (strs[0][i] * v[0] + strs[1][i] * v[1] + strs[2][i] * v[2]) % 3;
			nstrs.push_back(cur);
		}
		strs = nstrs;
	}

	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] |= cnt_good == (int)st.size();
			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 (curl >= r || curr <= l) {
						if (iteration == 0) {
							continue;
						} else {
							break;
						}
					}
					int cl = max(curl, l), cr = min(curr, r);
					erased.push_back({{curl, curr}, curc});
					inserted.push_back({{curl, cl}, curc});
					inserted.push_back({{cl, cr}, c});
					inserted.push_back({{cr, curr}, curc});
				}
				for (auto seg : erased) erase(seg.first.first, seg.first.second, seg.second);
				{
					vector<pair<pair<int, int>, int>> compressed;
					for (auto seg : inserted) {
						int curl = seg.first.first, curr = seg.first.second, curc = seg.second;
						if (curl >= curr) continue;
						if (compressed.empty() || curl > compressed.back().first.second || curc != compressed.back().second) {
							compressed.push_back({{curl, curr}, curc});
						} else {
							compressed.back().first.second = curr;
						}
					}
					inserted = compressed;
				}
				for (auto seg : inserted) 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