Submission #799921

#	Time	Username	Problem	Language	Result	Execution time	Memory
799921		NothingXD	Crossing (JOI21_crossing)	C++17	100 / 100	682 ms	21556 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int alpha = 27;
int base[2] = {313, 369}, mod[2] = {(int)1e9+7, (int)1e9+9};

int n, q, a[maxn][3], pw[maxn][2], val[maxn][3][2], seg[maxn << 2][2], lazy[maxn << 2];
int hsh[alpha][2];
bool mark[alpha];
void shift(int v, int l, int r);

void change(int v, int l, int r, int ql, int qr, int x){
	//if (v == 1) debug(ql, qr, x);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
	//	debug(l, r, x);
		seg[v][0] = val[r-l][x][0];
		seg[v][1] = val[r-l][x][1];
		lazy[v] = x;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, ql, qr, x);
	change(v << 1 | 1, mid, r, ql, qr, x);
	for (int i = 0; i < 2; i++){
		seg[v][i] = (1ll * seg[v << 1][i] * pw[r-mid][i] + seg[v << 1 | 1][i]) % mod[i];
	}
}

void shift(int v, int l, int r){
	if (lazy[v] == -1) return;
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, l, mid, lazy[v]);
	change(v << 1 | 1, mid, r, mid, r, lazy[v]);
	lazy[v] = -1;
}


bool check(){
	//return MP(hsh[1][0], hsh[1][1]) == MP(seg[1][0], seg[1][1]);
	for (int i = 0; i < alpha; i++){
		if (mark[i] && MP(hsh[i][0], hsh[i][1]) == MP(seg[1][0], seg[1][1])){
		//	debug(i);
			return true;
		}
	}
	return false;
}

int main(){

	memset(lazy, -1, sizeof lazy);

	string s[3];

	cin >> n >> s[0] >> s[1] >> s[2];
	for (int j = 0; j < 3; j++){
		for (int i = 1; i <= n; i++){
			a[i][j] = (s[j][i-1] == 'J'? 0: (s[j][i-1] == 'O'? 1: 2));
		//	debug(i, j, a[i][j]);
		}
	}

	pw[0][0] = pw[0][1] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 2; j++){
			pw[i][j] = 1ll * pw[i-1][j] * base[j] % mod[j];
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 3; j++){
			for (int k = 0; k < 2; k++){
				val[i][j][k] = (1ll * val[i-1][j][k] * base[k] + (j+1)) % mod[k];
			}
		}
	}

	for (int x1 = 0; x1 < 3; x1++){
		for (int x2 = 0; x2 < 3; x2++){
			for (int x3 = 0; x3 < 3; x3++){
				if ((x1 + x2 + x3) % 3 != 1) continue;
				int idx = x3 + x2 * 3 + x1 * 9;
			//	debug(x1, x2, x3, idx);
				mark[idx] = true;
				for (int i = 1; i <= n; i++){
					int tmp = (a[i][0] * x1 + a[i][1] * x2 + a[i][2] * x3) % 3;
				//	if (x1 == 0 && x2 == 0 && x3 == 2) debug(i, tmp);
					for (int j = 0; j < 2; j++){
						hsh[idx][j] = (1ll * hsh[idx][j] * base[j] + (tmp+1)) % mod[j];
					}
				}
			}
		}
	}

	cin >> q;
	string t;
	cin >> t;
	for (int i = 1; i <= n; i++){
		int tmp = (t[i-1] == 'J'? 0: (t[i-1] == 'O'? 1: 2));
		change(1, 1, n+1, i, i+1, tmp);
	}
	cout << (check()? "Yes\n": "No\n");
	while(q--){
		int l, r; char c; cin >> l >> r >> c;
		
		int tmp = (c == 'J'? 0: (c == 'O'? 1: 2));
		change(1, 1, n+1, l, r+1, tmp);
		cout << (check()? "Yes\n": "No\n");
	}

	return 0;
}

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