Submission #1280655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280655		am_aadvik	Crossing (JOI21_crossing)	C++20	100 / 100	2402 ms	86704 KiB

Main

#include <iostream>
#include <map>
#include<vector>
using namespace std;

int conv(char c) { if (c == 'J')return 0; if (c == 'O') return 1; else return 2; }
string t, v = "JOI";
class prefix {
public:
	string s; int n;
	vector<int> pre[3];
	void set(string q, int N) {
		s = q, n = N;
		for (int i = 0; i < 3; ++i)
			pre[i].assign(n, 0);
		for (int j = 0; j < 3; ++j)
			for (int i = 0; i < n; ++i)
				pre[j][i] = (((i == 0) ? 0 : pre[j][i - 1]) + (s[i] == v[j]));
	}
	int query(int l, int r, int j) { 
		return pre[j][r] - ((l == 0) ? 0 : pre[j][l - 1]); 
	}
};
class segtree {
private:
	vector<int> st, lazy;
	string a; prefix p;
	const int dv = 0;
	const int ldv = 3;
	int join(int l, int r) {
		return l & r;
	}
	int ljoin(int l, int r) {
		return ((r == 3) ? l : r);
	}
	void upd(int s, int e, int node, int val) {
		if (val == ldv) return;
		int cnt = p.query(s, e, val);
		st[node] = (cnt == (e - s + 1));
	}
	int build(int s, int e, int node) {
		if (s == e)
			return st[node] = (t[s] == a[s]);
		int mid = (s + e) / 2;
		return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
	}
	void update(int s, int e, int node, int l, int r, int val) {
		if ((l > e) || (r < s)) return;
		if ((l <= s) && (r >= e)) {
			upd(s, e, node, val);
			lazy[node] = ljoin(lazy[node], val);
			return;
		}
		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;
		update(s, mid, node * 2, l, r, val);
		update(mid + 1, e, node * 2 + 1, l, r, val);
		st[node] = join(st[node * 2], st[node * 2 + 1]);
	}

public:
	void assign(int n, string s) {
		a = s, p.set(s, n);
		st.resize(4 * n, dv);
		lazy.resize(4 * n, ldv);
		build(0, n - 1, 1);
	}
	int query() { return st[1]; }
	void update(int l, int r, char val) {
		update(0, a.length() - 1, 1, l, r, conv(val));
	}
};
string op(string& a, string& b) {
	string res = "";
	for (int i = 0; i < a.length(); ++i)
		if (a[i] == b[i]) res += a[i];
		else
			for (auto x : v)
				if ((a[i] != x) && (b[i] != x))
					res += x;
	return res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	vector<string> a(3);
	cin >> a[0] >> a[1] >> a[2];
	map<string, bool> mp;
	for (auto x : a) mp[x] = 1;
	while (1) {
		bool c = 0;
		for (auto x : a) {
			for (auto y : a) {
				auto r = op(x, y);
				if (!mp[r]) { c = 1, a.push_back(r), mp[r] = 1; break; }
			}
			if (c) break;
		}
		if (!c) break;
	}

	int q, m = a.size(), res = 0; cin >> q;
	cin >> t;
	vector<segtree> st(m);
	for (int i = 0; i < m; ++i)
		st[i].assign(n, a[i]),
		res |= st[i].query();
	cout << (res ? "Yes" : "No") << endl;
	while (q--) {
		int l, r; cin >> l >> r; --l, --r;
		char val; cin >> val; res = 0;
		for (auto& x : st)
			x.update(l, r, val),
			res |= x.query();
		cout << (res ? "Yes" : "No") << endl;
	}
}

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