oj.uz

Submission #799914

# Submission time Handle Problem Language Result Execution time Memory
799914 2023-08-01T08:18:59 Z NothingXD Crossing (JOI21_crossing) C++17
26 / 100
 667 ms 21512 KB 
#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 == 0) 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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 5300 KB Output is correct
2 Correct 307 ms 5280 KB Output is correct
3 Correct 316 ms 5388 KB Output is correct
4 Correct 289 ms 5284 KB Output is correct
5 Correct 317 ms 5288 KB Output is correct
6 Correct 283 ms 5212 KB Output is correct
7 Correct 298 ms 5232 KB Output is correct
8 Correct 309 ms 5288 KB Output is correct
9 Correct 305 ms 5308 KB Output is correct
10 Correct 307 ms 5256 KB Output is correct
11 Correct 300 ms 5296 KB Output is correct
12 Correct 304 ms 5320 KB Output is correct
13 Correct 304 ms 5308 KB Output is correct
14 Correct 297 ms 5232 KB Output is correct
15 Correct 302 ms 5260 KB Output is correct
16 Correct 298 ms 5332 KB Output is correct
17 Correct 315 ms 5244 KB Output is correct
18 Correct 304 ms 5272 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 5300 KB Output is correct
2 Correct 307 ms 5280 KB Output is correct
3 Correct 316 ms 5388 KB Output is correct
4 Correct 289 ms 5284 KB Output is correct
5 Correct 317 ms 5288 KB Output is correct
6 Correct 283 ms 5212 KB Output is correct
7 Correct 298 ms 5232 KB Output is correct
8 Correct 309 ms 5288 KB Output is correct
9 Correct 305 ms 5308 KB Output is correct
10 Correct 307 ms 5256 KB Output is correct
11 Correct 300 ms 5296 KB Output is correct
12 Correct 304 ms 5320 KB Output is correct
13 Correct 304 ms 5308 KB Output is correct
14 Correct 297 ms 5232 KB Output is correct
15 Correct 302 ms 5260 KB Output is correct
16 Correct 298 ms 5332 KB Output is correct
17 Correct 315 ms 5244 KB Output is correct
18 Correct 304 ms 5272 KB Output is correct
19 Correct 643 ms 18888 KB Output is correct
20 Correct 651 ms 20708 KB Output is correct
21 Correct 537 ms 20480 KB Output is correct
22 Correct 542 ms 19432 KB Output is correct
23 Correct 384 ms 7116 KB Output is correct
24 Correct 366 ms 7148 KB Output is correct
25 Correct 556 ms 21284 KB Output is correct
26 Correct 564 ms 21228 KB Output is correct
27 Correct 578 ms 21228 KB Output is correct
28 Correct 588 ms 21288 KB Output is correct
29 Correct 567 ms 20988 KB Output is correct
30 Correct 377 ms 7040 KB Output is correct
31 Correct 595 ms 21228 KB Output is correct
32 Correct 560 ms 20272 KB Output is correct
33 Correct 367 ms 7044 KB Output is correct
34 Correct 608 ms 21256 KB Output is correct
35 Correct 497 ms 18472 KB Output is correct
36 Correct 368 ms 7036 KB Output is correct
37 Correct 374 ms 7096 KB Output is correct
38 Correct 607 ms 21092 KB Output is correct
39 Correct 539 ms 21348 KB Output is correct
40 Correct 550 ms 15716 KB Output is correct
41 Correct 667 ms 21512 KB Output is correct
42 Correct 426 ms 20788 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 5300 KB Output is correct
2 Correct 307 ms 5280 KB Output is correct
3 Correct 316 ms 5388 KB Output is correct
4 Correct 289 ms 5284 KB Output is correct
5 Correct 317 ms 5288 KB Output is correct
6 Correct 283 ms 5212 KB Output is correct
7 Correct 298 ms 5232 KB Output is correct
8 Correct 309 ms 5288 KB Output is correct
9 Correct 305 ms 5308 KB Output is correct
10 Correct 307 ms 5256 KB Output is correct
11 Correct 300 ms 5296 KB Output is correct
12 Correct 304 ms 5320 KB Output is correct
13 Correct 304 ms 5308 KB Output is correct
14 Correct 297 ms 5232 KB Output is correct
15 Correct 302 ms 5260 KB Output is correct
16 Correct 298 ms 5332 KB Output is correct
17 Correct 315 ms 5244 KB Output is correct
18 Correct 304 ms 5272 KB Output is correct
19 Correct 302 ms 5300 KB Output is correct
20 Correct 338 ms 5356 KB Output is correct
21 Incorrect 310 ms 5276 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 5300 KB Output is correct
2 Correct 307 ms 5280 KB Output is correct
3 Correct 316 ms 5388 KB Output is correct
4 Correct 289 ms 5284 KB Output is correct
5 Correct 317 ms 5288 KB Output is correct
6 Correct 283 ms 5212 KB Output is correct
7 Correct 298 ms 5232 KB Output is correct
8 Correct 309 ms 5288 KB Output is correct
9 Correct 305 ms 5308 KB Output is correct
10 Correct 307 ms 5256 KB Output is correct
11 Correct 300 ms 5296 KB Output is correct
12 Correct 304 ms 5320 KB Output is correct
13 Correct 304 ms 5308 KB Output is correct
14 Correct 297 ms 5232 KB Output is correct
15 Correct 302 ms 5260 KB Output is correct
16 Correct 298 ms 5332 KB Output is correct
17 Correct 315 ms 5244 KB Output is correct
18 Correct 304 ms 5272 KB Output is correct
19 Correct 643 ms 18888 KB Output is correct
20 Correct 651 ms 20708 KB Output is correct
21 Correct 537 ms 20480 KB Output is correct
22 Correct 542 ms 19432 KB Output is correct
23 Correct 384 ms 7116 KB Output is correct
24 Correct 366 ms 7148 KB Output is correct
25 Correct 556 ms 21284 KB Output is correct
26 Correct 564 ms 21228 KB Output is correct
27 Correct 578 ms 21228 KB Output is correct
28 Correct 588 ms 21288 KB Output is correct
29 Correct 567 ms 20988 KB Output is correct
30 Correct 377 ms 7040 KB Output is correct
31 Correct 595 ms 21228 KB Output is correct
32 Correct 560 ms 20272 KB Output is correct
33 Correct 367 ms 7044 KB Output is correct
34 Correct 608 ms 21256 KB Output is correct
35 Correct 497 ms 18472 KB Output is correct
36 Correct 368 ms 7036 KB Output is correct
37 Correct 374 ms 7096 KB Output is correct
38 Correct 607 ms 21092 KB Output is correct
39 Correct 539 ms 21348 KB Output is correct
40 Correct 550 ms 15716 KB Output is correct
41 Correct 667 ms 21512 KB Output is correct
42 Correct 426 ms 20788 KB Output is correct
43 Correct 302 ms 5300 KB Output is correct
44 Correct 338 ms 5356 KB Output is correct
45 Incorrect 310 ms 5276 KB Output isn't correct
46 Halted 0 ms 0 KB -