Submission #800141

#	Time	Username	Problem	Language	Result	Execution time	Memory
800141		fatemetmhr	Crossing (JOI21_crossing)	C++17	0 / 100	97 ms	11132 KiB

Main

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair


const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;

ll mod[2] = {1000000007, 1000000009};
ll base[2] = {21163, 21269};

int n, t[maxn5];
pair <ll, ll> hsh[maxnt];
int lazy[maxnt];
string s[3];
ll pw[2][maxn5], ps[2][maxn5];
set <pair<ll, ll>> av;
bool mark[100];

int get_val(char c){
	if(c == 'J')
		return 0;
	if(c == 'O')
		return 1;
	return 2;
}

struct zarib{

	int x[3];
	int num;
	zarib(){
		x[0] = x[1] = x[2] = num = 0;
	}

} q[100];

zarib comb(zarib a, zarib b){
	zarib ret;
	//cout << a.x[0] << ' ' << b.x[0] << endl;
	ret.x[0] = (6 - a.x[0] - b.x[0]) % 3;
	ret.x[1] = (6 - a.x[1] - b.x[1]) % 3;
	ret.x[2] = (6 - a.x[2] - b.x[2]) % 3;
	ret.num = ret.x[0] + ret.x[1] * 3 + ret.x[2] * 9;
	//cout << ret.x[0]  << ' ' << ret.x[1] << ' ' << ret.x[2] << ' ' << ret.num << endl;
	return ret;
}

void shift(int, int, int);

void build(int l, int r, int v){
	if(r - l == 1){
		hsh[v].fi = t[l] * pw[0][n - l - 1] % mod[1];
		hsh[v].se = t[l] * pw[1][n - l - 1] % mod[0];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	hsh[v].fi = (hsh[v * 2].fi + hsh[v * 2 + 1].fi) % mod[0];
	hsh[v].se = (hsh[v * 2].se + hsh[v * 2 + 1].se) % mod[1];
}

void upd(int l, int r, int lq, int rq, int val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		lazy[v] = val;
		hsh[v].fi = (mod[0] + ps[0][n - l - 1] - (r == n ? 0 : ps[0][n - r - 1])) % mod[0] * val % mod[0];
		hsh[v].se = (mod[1] + ps[1][n - l - 1] - (r == n ? 0 : ps[1][n - r - 1])) % mod[1] * val % mod[1];
		return;
	}
	int mid = (l + r) >> 1;
	shift(l, r, v);
	upd(l, mid, lq, rq, val, v * 2);
	upd(mid, r, lq, rq, val, v * 2 + 1);
	hsh[v].fi = (hsh[v * 2].fi + hsh[v * 2 + 1].fi) % mod[0];
	hsh[v].se = (hsh[v * 2].se + hsh[v * 2 + 1].se) % mod[1];
}

void shift(int l, int r, int v){
	if(lazy[v] == -1)
		return;
	int mid = (l + r) >> 1;
	upd(l, mid, l, mid, lazy[v], v * 2);
	upd(mid, r, mid, r, lazy[v], v * 2 + 1);
	lazy[v] = -1;
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	memset(lazy, -1, sizeof lazy);

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

	for(int tt = 0; tt < 2; tt++){
		pw[tt][0] = 1;
		for(int i = 1; i < maxn5; i++)
			pw[tt][i] = (pw[tt][i - 1] * base[tt]) % mod[tt];
		ps[tt][0] = 1;
		for(int i = 1; i < maxn5; i++)
			ps[tt][i] = (ps[tt][i - 1] + pw[tt][i]) % mod[tt];
	}

	zarib a, b, c;
	a.x[0] = b.x[1] = c.x[2] = 1;
	a.num = 1;
	b.num = 3;
	c.num = 9;
	q[0] = a;
	q[1] = b;
	q[2] = c;
	int l = 0, r = 3;
	while(l < r){
		zarib a = q[l];
		for(int i = 0; i < l; i++){
			zarib x = comb(a, q[i]);
			if(!mark[x.num]){
				q[r++] = x;
				mark[x.num] = true;
			}
		}
		l++;
	}

	for(int i = 0; i < r; i++){
		ll val[2] = {0, 0};
		for(int j = 0; j < n; j++){
			int a = (get_val(s[0][j]) * q[i].x[0] + get_val(s[1][j]) * q[i].x[1] + get_val(s[2][j]) * q[i].x[2]) % 3; 
			val[0] = (val[0] * base[0] + a) % mod[0];
			val[1] = (val[1] * base[1] + a) % mod[1];
		}
		//cout << i << ' ' << val[0] << ' ' << val[1] << endl;
		av.insert(mp(val[0], val[1]));
	}
	assert(av.size() == 1);

	string tm; int q;
	cin >> q >> tm;
	for(int i = 0; i < n; i++)
		t[i] = get_val(tm[i]);
	build(0, n, 1);
	//cout << hsh[1].fi << ' ' << hsh[1].se << endl;
	cout << (av.find(hsh[1]) != av.end() ? "Yes\n" : "No\n");
	while(q--){
		int l, r; char c; cin >> l >> r >> c;
		int a = get_val(c);
		upd(0, n, l - 1, r, a, 1);
		cout << (av.find(hsh[1]) != av.end() ? "Yes\n" : "No\n");
	}
}

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