oj.uz

Submission #445969

# Submission time Handle Problem Language Result Execution time Memory
445969 2021-07-20T09:56:46 Z dutch Crossing (JOI21_crossing) C++17
100 / 100
 2047 ms 40880 KB 
#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 push(int x, int lx, int rx){
	assert(2*x+2 < 2*LIM);
	if(a[x] == 3) return;
	
	int mx = (lx + rx) / 2;
	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);
}

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;
	push(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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 38564 KB Output is correct
2 Correct 546 ms 38632 KB Output is correct
3 Correct 630 ms 38436 KB Output is correct
4 Correct 456 ms 38508 KB Output is correct
5 Correct 430 ms 38540 KB Output is correct
6 Correct 433 ms 38468 KB Output is correct
7 Correct 453 ms 38544 KB Output is correct
8 Correct 430 ms 38628 KB Output is correct
9 Correct 461 ms 38596 KB Output is correct
10 Correct 453 ms 38568 KB Output is correct
11 Correct 430 ms 38532 KB Output is correct
12 Correct 451 ms 38596 KB Output is correct
13 Correct 457 ms 38664 KB Output is correct
14 Correct 440 ms 38708 KB Output is correct
15 Correct 447 ms 38704 KB Output is correct
16 Correct 451 ms 38708 KB Output is correct
17 Correct 437 ms 38632 KB Output is correct
18 Correct 579 ms 38560 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 38564 KB Output is correct
2 Correct 546 ms 38632 KB Output is correct
3 Correct 630 ms 38436 KB Output is correct
4 Correct 456 ms 38508 KB Output is correct
5 Correct 430 ms 38540 KB Output is correct
6 Correct 433 ms 38468 KB Output is correct
7 Correct 453 ms 38544 KB Output is correct
8 Correct 430 ms 38628 KB Output is correct
9 Correct 461 ms 38596 KB Output is correct
10 Correct 453 ms 38568 KB Output is correct
11 Correct 430 ms 38532 KB Output is correct
12 Correct 451 ms 38596 KB Output is correct
13 Correct 457 ms 38664 KB Output is correct
14 Correct 440 ms 38708 KB Output is correct
15 Correct 447 ms 38704 KB Output is correct
16 Correct 451 ms 38708 KB Output is correct
17 Correct 437 ms 38632 KB Output is correct
18 Correct 579 ms 38560 KB Output is correct
19 Correct 1869 ms 40820 KB Output is correct
20 Correct 1718 ms 40680 KB Output is correct
21 Correct 601 ms 40464 KB Output is correct
22 Correct 644 ms 40192 KB Output is correct
23 Correct 404 ms 39256 KB Output is correct
24 Correct 433 ms 39500 KB Output is correct
25 Correct 606 ms 40660 KB Output is correct
26 Correct 732 ms 40624 KB Output is correct
27 Correct 953 ms 40776 KB Output is correct
28 Correct 971 ms 40740 KB Output is correct
29 Correct 883 ms 40808 KB Output is correct
30 Correct 504 ms 39304 KB Output is correct
31 Correct 909 ms 40560 KB Output is correct
32 Correct 858 ms 40420 KB Output is correct
33 Correct 466 ms 39500 KB Output is correct
34 Correct 946 ms 40624 KB Output is correct
35 Correct 540 ms 40360 KB Output is correct
36 Correct 432 ms 39560 KB Output is correct
37 Correct 424 ms 39628 KB Output is correct
38 Correct 1512 ms 40532 KB Output is correct
39 Correct 370 ms 40836 KB Output is correct
40 Correct 637 ms 40452 KB Output is correct
41 Correct 2047 ms 40880 KB Output is correct
42 Correct 343 ms 40076 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 38564 KB Output is correct
2 Correct 546 ms 38632 KB Output is correct
3 Correct 630 ms 38436 KB Output is correct
4 Correct 456 ms 38508 KB Output is correct
5 Correct 430 ms 38540 KB Output is correct
6 Correct 433 ms 38468 KB Output is correct
7 Correct 453 ms 38544 KB Output is correct
8 Correct 430 ms 38628 KB Output is correct
9 Correct 461 ms 38596 KB Output is correct
10 Correct 453 ms 38568 KB Output is correct
11 Correct 430 ms 38532 KB Output is correct
12 Correct 451 ms 38596 KB Output is correct
13 Correct 457 ms 38664 KB Output is correct
14 Correct 440 ms 38708 KB Output is correct
15 Correct 447 ms 38704 KB Output is correct
16 Correct 451 ms 38708 KB Output is correct
17 Correct 437 ms 38632 KB Output is correct
18 Correct 579 ms 38560 KB Output is correct
19 Correct 479 ms 38512 KB Output is correct
20 Correct 572 ms 38468 KB Output is correct
21 Correct 419 ms 38680 KB Output is correct
22 Correct 407 ms 38376 KB Output is correct
23 Correct 419 ms 38628 KB Output is correct
24 Correct 418 ms 38496 KB Output is correct
25 Correct 428 ms 38724 KB Output is correct
26 Correct 425 ms 38472 KB Output is correct
27 Correct 423 ms 38624 KB Output is correct
28 Correct 416 ms 38336 KB Output is correct
29 Correct 432 ms 38648 KB Output is correct
30 Correct 405 ms 38644 KB Output is correct
31 Correct 432 ms 38756 KB Output is correct
32 Correct 427 ms 38508 KB Output is correct
33 Correct 429 ms 38544 KB Output is correct
34 Correct 414 ms 38524 KB Output is correct
35 Correct 415 ms 38572 KB Output is correct
36 Correct 434 ms 38616 KB Output is correct
37 Correct 415 ms 38600 KB Output is correct
38 Correct 492 ms 38652 KB Output is correct
39 Correct 422 ms 38560 KB Output is correct
40 Correct 427 ms 38644 KB Output is correct
41 Correct 416 ms 38652 KB Output is correct
42 Correct 429 ms 38776 KB Output is correct
43 Correct 429 ms 38596 KB Output is correct
44 Correct 428 ms 38780 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 38564 KB Output is correct
2 Correct 546 ms 38632 KB Output is correct
3 Correct 630 ms 38436 KB Output is correct
4 Correct 456 ms 38508 KB Output is correct
5 Correct 430 ms 38540 KB Output is correct
6 Correct 433 ms 38468 KB Output is correct
7 Correct 453 ms 38544 KB Output is correct
8 Correct 430 ms 38628 KB Output is correct
9 Correct 461 ms 38596 KB Output is correct
10 Correct 453 ms 38568 KB Output is correct
11 Correct 430 ms 38532 KB Output is correct
12 Correct 451 ms 38596 KB Output is correct
13 Correct 457 ms 38664 KB Output is correct
14 Correct 440 ms 38708 KB Output is correct
15 Correct 447 ms 38704 KB Output is correct
16 Correct 451 ms 38708 KB Output is correct
17 Correct 437 ms 38632 KB Output is correct
18 Correct 579 ms 38560 KB Output is correct
19 Correct 1869 ms 40820 KB Output is correct
20 Correct 1718 ms 40680 KB Output is correct
21 Correct 601 ms 40464 KB Output is correct
22 Correct 644 ms 40192 KB Output is correct
23 Correct 404 ms 39256 KB Output is correct
24 Correct 433 ms 39500 KB Output is correct
25 Correct 606 ms 40660 KB Output is correct
26 Correct 732 ms 40624 KB Output is correct
27 Correct 953 ms 40776 KB Output is correct
28 Correct 971 ms 40740 KB Output is correct
29 Correct 883 ms 40808 KB Output is correct
30 Correct 504 ms 39304 KB Output is correct
31 Correct 909 ms 40560 KB Output is correct
32 Correct 858 ms 40420 KB Output is correct
33 Correct 466 ms 39500 KB Output is correct
34 Correct 946 ms 40624 KB Output is correct
35 Correct 540 ms 40360 KB Output is correct
36 Correct 432 ms 39560 KB Output is correct
37 Correct 424 ms 39628 KB Output is correct
38 Correct 1512 ms 40532 KB Output is correct
39 Correct 370 ms 40836 KB Output is correct
40 Correct 637 ms 40452 KB Output is correct
41 Correct 2047 ms 40880 KB Output is correct
42 Correct 343 ms 40076 KB Output is correct
43 Correct 479 ms 38512 KB Output is correct
44 Correct 572 ms 38468 KB Output is correct
45 Correct 419 ms 38680 KB Output is correct
46 Correct 407 ms 38376 KB Output is correct
47 Correct 419 ms 38628 KB Output is correct
48 Correct 418 ms 38496 KB Output is correct
49 Correct 428 ms 38724 KB Output is correct
50 Correct 425 ms 38472 KB Output is correct
51 Correct 423 ms 38624 KB Output is correct
52 Correct 416 ms 38336 KB Output is correct
53 Correct 432 ms 38648 KB Output is correct
54 Correct 405 ms 38644 KB Output is correct
55 Correct 432 ms 38756 KB Output is correct
56 Correct 427 ms 38508 KB Output is correct
57 Correct 429 ms 38544 KB Output is correct
58 Correct 414 ms 38524 KB Output is correct
59 Correct 415 ms 38572 KB Output is correct
60 Correct 434 ms 38616 KB Output is correct
61 Correct 415 ms 38600 KB Output is correct
62 Correct 492 ms 38652 KB Output is correct
63 Correct 422 ms 38560 KB Output is correct
64 Correct 427 ms 38644 KB Output is correct
65 Correct 416 ms 38652 KB Output is correct
66 Correct 429 ms 38776 KB Output is correct
67 Correct 429 ms 38596 KB Output is correct
68 Correct 428 ms 38780 KB Output is correct
69 Correct 1435 ms 40200 KB Output is correct
70 Correct 1462 ms 40700 KB Output is correct
71 Correct 424 ms 39540 KB Output is correct
72 Correct 435 ms 39324 KB Output is correct
73 Correct 427 ms 39252 KB Output is correct
74 Correct 556 ms 40664 KB Output is correct
75 Correct 408 ms 39552 KB Output is correct
76 Correct 597 ms 40752 KB Output is correct
77 Correct 649 ms 40388 KB Output is correct
78 Correct 428 ms 39500 KB Output is correct
79 Correct 423 ms 39332 KB Output is correct
80 Correct 606 ms 40164 KB Output is correct
81 Correct 419 ms 39544 KB Output is correct
82 Correct 591 ms 40624 KB Output is correct
83 Correct 664 ms 40332 KB Output is correct
84 Correct 420 ms 39628 KB Output is correct
85 Correct 419 ms 39632 KB Output is correct
86 Correct 900 ms 40224 KB Output is correct
87 Correct 907 ms 40800 KB Output is correct
88 Correct 488 ms 39380 KB Output is correct
89 Correct 738 ms 40224 KB Output is correct
90 Correct 794 ms 40784 KB Output is correct
91 Correct 486 ms 39500 KB Output is correct
92 Correct 529 ms 40164 KB Output is correct
93 Correct 424 ms 39556 KB Output is correct
94 Correct 419 ms 39588 KB Output is correct
95 Correct 419 ms 39508 KB Output is correct
96 Correct 1643 ms 40588 KB Output is correct
97 Correct 367 ms 40620 KB Output is correct
98 Correct 582 ms 40376 KB Output is correct
99 Correct 1710 ms 40836 KB Output is correct
100 Correct 307 ms 40236 KB Output is correct