Submission #1279444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279444		janson0109	Crossing (JOI21_crossing)	C++20	100 / 100	625 ms	31736 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 1000000007;

template <typename T> class LazySegtree {
  private:
	const int sz;
	const T DEFAULT;
	vector<int> tree;
	vector<T> lazy;
	vector<vector<T>> orig;
	vector<vector<int>> chain;
	void find_chain() {
		for(auto &x : orig) {
			chain.push_back(vector<int> (x.size()));
			chain.back().back() = 1;
			for(int i=x.size()-2; i>=0; i--) chain.back()[i] = (x[i] == x[i+1] ? chain.back()[i+1]+1 : 1);
		}
	}

	int check(int v, int len, T ch) {
		int ans = 0;
		for(int i=0; i<orig.size(); i++) if(chain[i][v] >= len && orig[i][v] == ch) ans += (1 << i);
		return ans;
	}

	void apply(int v, int l, int len, T ch) {
		tree[v] = check(l, len, ch);
		lazy[v] = ch;
	}

	/** pushes down lazy updates to children of v */
	void push_down(int v, int l, int r) {
		if(lazy[v] == DEFAULT) return;
		int m = (l + r) / 2;
		apply(2 * v, l, m - l + 1, lazy[v]);
		apply(2 * v + 1, m+1, r - m, lazy[v]);
		lazy[v] = DEFAULT;
	}

	void range_set(int v, int l, int r, int ql, int qr, T ch) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, l, r - l + 1, ch);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_set(2 * v, l, m, ql, qr, ch);
			range_set(2 * v + 1, m + 1, r, ql, qr, ch);
			tree[v] = tree[2 * v] & tree[2 * v + 1];
		}
	}

	int range_sum(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return INT_MAX; }
		if (ql <= l && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) / 2;
		return (range_sum(2 * v, l, m, ql, qr) & range_sum(2 * v + 1, m + 1, r, ql, qr));
	}

  public:
	LazySegtree(int n, vector<vector<T>> &orig, T def) : sz(n), orig(orig), DEFAULT(def), tree(4 * n), lazy(4 * n) {find_chain();}

	void range_set(int ql, int qr, T add) { range_set(1, 0, sz - 1, ql, qr, add); }

	int range_sum(int ql, int qr) { return range_sum(1, 0, sz - 1, ql, qr); }
};

int main() {
	lol
	int n, q;
	cin >> n;
	vector<vector<int>> s(3, vector<int>(n));
	for(int i=0; i<3; i++) for(int j=0; j<n; j++) {
		char ch; cin >> ch;
		s[i][j] = (ch == 'J' ? 0 : (ch == 'O' ? 1 : 2));
	}
	vector<vector<int>> orig;
	for(int i=0; i<3; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++) if((i + j + k) % 3 == 1) {
		vector<int> x(n);
		for(int a=0; a<n; a++) x[a] = (i*s[0][a] + j*s[1][a] + k*s[2][a]) % 3;
		orig.push_back(x);
	}
	string t0;
	cin >> q >> t0;
	LazySegtree<int> seg(n, orig, 3);
	for(int i=0; i<n; i++) seg.range_set(i, i, t0[i] == 'J' ? 0 : (t0[i] == 'O' ? 1 : 2));
	cout << (seg.range_sum(0, n-1) ? "Yes\n" : "No\n"); 
	for(int i=0; i<q; i++) {
		int l, r; char ch;
		cin >> l >> r >> ch;
		seg.range_set(l-1, r-1, ch == 'J' ? 0 : (ch == 'O' ? 1 : 2));
		cout << (seg.range_sum(0, n-1) ? "Yes\n" : "No\n"); 
	}
}

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