Submission #445970

#	Time	Username	Problem	Language	Result	Execution time	Memory
445970		dutch	Crossing (JOI21_crossing)	C++17	100 / 100	1830 ms	37576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define get(c) (c == 'I' ? 2 : c == 'O')

const int LIM = 1<<18;

int n, q, l, r, p[3][9][LIM];
string s[10];

short a[2*LIM], v;
bool b[9][2*LIM];

void pull(int x, int lx, int rx){
	for(int i=0; i<9; ++i){
		if(a[x] == 3){
			assert(2*x+2 < 2*LIM);
			b[i][x] = b[i][2*x+1] && b[i][2*x+2];
		}else{
			int sum = p[a[x]][i][rx-1] - (lx ? p[a[x]][i][lx-1] : 0);
			b[i][x] = sum == rx - lx;
		}
	}
}

void build(int x, int lx, int rx){
	if(rx - lx < 2){
		a[x] = get(s[9][lx]);
		pull(x, lx, rx);
		return;
	}
	int mx = (lx + rx) / 2;
	build(2*x+1, lx, mx);
	build(2*x+2, mx, rx);
	pull(x, lx, rx);
}

void rangeAssign(int x, int lx, int rx){
	if(r<=lx || rx<=l) return;
	if(l<=lx && rx<=r){
		a[x] = v;
		pull(x, lx, rx);
		return;
	}
	int mx = (lx + rx) / 2;
	if(a[x] < 3){
		a[2*x+1] = a[2*x+2] = a[x];
		a[x] = 3;
		pull(2*x+1, lx, mx);
		pull(2*x+2, mx, rx);
		pull(x, lx, rx);
	}
	rangeAssign(2*x+1, lx, mx);
	rangeAssign(2*x+2, mx, rx);
	pull(x, lx, rx);
}

void print(){
	for(int i=0; i<9; ++i) if(b[i][0]) return void(cout << "Yes\n");
	cout << "No\n";
}

string comb(string &x, string &y){
	string z(n, 0);
	for(int i=0; i<n; ++i){
		z[i] = x[i] == y[i] ? x[i] : 226 - x[i] - y[i];
	}
	return z;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;

	cin >> s[0] >> s[1] >> s[2];

	s[3] = comb(s[1], s[2]);
	s[4] = comb(s[0], s[2]);
	s[5] = comb(s[0], s[1]);

	for(int i=0; i<3; ++i){
		s[6+i] = comb(s[i], s[3+i]);
	}

	fill(a, a+2*LIM, 3);

	cin >> q >> s[9];
	for(int i=0; i<10; ++i){
		s[i] += string(LIM-n, 'J');
	}
	for(int i=0; i<3; ++i){
		for(int j=0; j<9; ++j){
			int pre = 0;
			for(int k=0; k<LIM; ++k){
				pre += get(s[j][k]) == i;
				p[i][j][k] = pre;
			}
		}
	}

	build(0, 0, LIM);

	char inp;
	print();
	while(q--){
		cin >> l >> r >> inp;
		--l; v = get(inp);
		rangeAssign(0, 0, LIM);
		print();
	}
}

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