#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2*1e5;
struct Node{
bool ok;
int v;
Node(bool _ok, int _v){
ok = _ok;
v= _v;
}
Node(){
ok = true;
}
};
Node op(Node& a, Node& b){
if(a.ok && b.ok){
if(a.v == b.v){
return Node(true, a.v);
}
return Node(false, -1);
}
return Node(false, -1);
}
struct Tree{
int s, m;
map<int, int> small;
vector<Node> tree;
vector<Node> model;
vector<bool> ac;
vector<Node> d;
Tree(){s= 0;};
Tree (vector<Node>& mo, vector<Node>& v, map<int, int> sm){
s = v.size();
m = 1;
while(m<s){
m*=2;
}
m*=2;
tree.resize(m);
d.resize(m);
model.resize(m);
ac.resize(m, false);
swap(small, sm);
build(v,mo, 0, s-1, 1);
}
void ap(int id){
tree[id] =d[id];
if(tree[id].ok && model[id].ok){
tree[id].v = (tree[id].v- model[id].v+3)%3;
}
else{
tree[id].ok = false;
}
}
void push(int t, int lt, int rt){
if(lt!=rt && ac[t]){
d[t*2] = d[t];
ac[t] = false;
ac[t*2] =true;
ac[t*2+1]=true;
d[t*2+1] = d[t];
ap(t*2);
ap(t*2+1);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
}
void build(vector<Node>&v, vector<Node>& mo, int lt, int rt, int t){
if(lt == rt){
model[t] = mo[lt];
d[t] = v[lt];
ap(t);
}
else{
int mid = (lt+rt)/2;
build(v,mo, lt, mid, t*2);
build(v,mo, mid+1, rt, t*2+1);
model[t]= op(model[t*2], model[t*2+1]);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
}
void update(int l, int r, Node v, int lt, int rt, int t){
if(l<=lt && rt<=r){
d[t] = v;
ac[t] = true;
ap(t);
}
else if(r<lt|| rt<l){
return;
}
else{
int mid = (lt+rt)/2;
push(t, lt, rt);
/*push(t*2, lt, mid);
push(t*2+1, mid+1, rt);*/
update(l, r, v, lt, mid, t*2);
update(l, r, v, mid+1, rt, t*2+1);
tree[t] = op(tree[t*2], tree[t*2+1]);
}
//cout<<lt<<" "<<rt<<" "<<tree[t].v<<endl;
}
void request(int l, int r, int v){
auto l_it = small.lower_bound(l);
auto r_it = small.upper_bound(r);
if(r_it==small.begin()){
return;
}
r_it--;
if(l_it!=small.end() && r_it!=small.end() && l_it->second <= r_it -> second){
//cout<<(l_it->first)<<" "<<(r_it->first)<<endl;
update(l_it->second, r_it->second, Node(true, v), 0, s-1, 1);
}
}
}forest[3][3];
int n, q, v[3][3], t[MAX_N][2];
bool is_set[3][3];
string s[3], r;
bool upd_val(int x, int y, int val){
if(!is_set[x][y]){
is_set[x][y] = true;
v[x][y] = val;
}
else{
if(v[x][y] != val){
return false;
}
}
return true;
}
signed main(){
cin>>n;
for(int i = 0; i<3; i++){
cin>>s[i];
}
map<char, int> m;
m['J'] = 0;
m['O'] = 1;
m['I'] = 2;
for(int i = 0; i<n; i++){
t[i][0] =(m[s[1][i]] -m[s[0][i]] +3)%3;
t[i][1] =(m[s[2][i]] - m[s[0][i]] + 3)%3;
}
fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);
cin>>q;
cin>>r;
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
vector<Node> v, mod;
map<int, int> small;
for(int i = 0; i<n; i++){
if(t[i][0] == x && t[i][1] == y){
v.push_back(Node(true, m[r[i]]));
mod.push_back(Node(true, m[s[0][i]]));
small.insert(pair<int, int>(i, small.size()));
}
}
if(v.size()>0){
forest[x][y] = Tree(mod, v, small);
}
}
}
bool ok = true;
is_set[0][0] = true;
v[0][0] =0;
for(int i = -1; i<q; i++){
ok = true;
fill(&is_set[0][0], &is_set[0][0] + sizeof(is_set), false);
is_set[0][0] = true;
if(i >=0){
int l, ri;
char c;
cin>>l>>ri>>c;
l--;
ri--;
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
if(forest[x][y].s>0){
forest[x][y].request(l, ri, m[c]);
}
}
}
}
for(int x=0; x<3; x++){
for(int y = 0; y<3; y++){
if(forest[x][y].s>0){
is_set[x][y] = forest[x][y].tree[1].ok;
ok &= forest[x][y].tree[1].ok;
v[x][y] = forest[x][y].tree[1].v;
if(x==0 && y==0){
ok &= v[x][y]==0;
}
}
}
}
for(int i = 0; i<9; i++){
for(int b= 0; b<9; b++){
for(int e = 0; e<9; e++){
if(is_set[b/3][b%3] && is_set[e/3][e%3]){
ok &= upd_val((e/3 + b/3)%3, (e+b)%3, (v[e/3][e%3] + v[b/3][b%3])%3);
}
}
}
}
if(ok){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
740 KB |
Output is correct |
2 |
Correct |
452 ms |
864 KB |
Output is correct |
3 |
Correct |
441 ms |
836 KB |
Output is correct |
4 |
Correct |
445 ms |
864 KB |
Output is correct |
5 |
Correct |
442 ms |
2336 KB |
Output is correct |
6 |
Correct |
429 ms |
2260 KB |
Output is correct |
7 |
Correct |
445 ms |
2280 KB |
Output is correct |
8 |
Correct |
459 ms |
2332 KB |
Output is correct |
9 |
Correct |
460 ms |
2552 KB |
Output is correct |
10 |
Correct |
458 ms |
2468 KB |
Output is correct |
11 |
Correct |
450 ms |
2352 KB |
Output is correct |
12 |
Correct |
452 ms |
2424 KB |
Output is correct |
13 |
Correct |
466 ms |
2340 KB |
Output is correct |
14 |
Correct |
451 ms |
2412 KB |
Output is correct |
15 |
Correct |
445 ms |
2496 KB |
Output is correct |
16 |
Correct |
445 ms |
2444 KB |
Output is correct |
17 |
Correct |
446 ms |
2316 KB |
Output is correct |
18 |
Correct |
470 ms |
2300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
740 KB |
Output is correct |
2 |
Correct |
452 ms |
864 KB |
Output is correct |
3 |
Correct |
441 ms |
836 KB |
Output is correct |
4 |
Correct |
445 ms |
864 KB |
Output is correct |
5 |
Correct |
442 ms |
2336 KB |
Output is correct |
6 |
Correct |
429 ms |
2260 KB |
Output is correct |
7 |
Correct |
445 ms |
2280 KB |
Output is correct |
8 |
Correct |
459 ms |
2332 KB |
Output is correct |
9 |
Correct |
460 ms |
2552 KB |
Output is correct |
10 |
Correct |
458 ms |
2468 KB |
Output is correct |
11 |
Correct |
450 ms |
2352 KB |
Output is correct |
12 |
Correct |
452 ms |
2424 KB |
Output is correct |
13 |
Correct |
466 ms |
2340 KB |
Output is correct |
14 |
Correct |
451 ms |
2412 KB |
Output is correct |
15 |
Correct |
445 ms |
2496 KB |
Output is correct |
16 |
Correct |
445 ms |
2444 KB |
Output is correct |
17 |
Correct |
446 ms |
2316 KB |
Output is correct |
18 |
Correct |
470 ms |
2300 KB |
Output is correct |
19 |
Correct |
843 ms |
38264 KB |
Output is correct |
20 |
Correct |
724 ms |
37976 KB |
Output is correct |
21 |
Correct |
678 ms |
36576 KB |
Output is correct |
22 |
Correct |
671 ms |
34336 KB |
Output is correct |
23 |
Correct |
525 ms |
5204 KB |
Output is correct |
24 |
Correct |
565 ms |
5120 KB |
Output is correct |
25 |
Correct |
745 ms |
38052 KB |
Output is correct |
26 |
Correct |
799 ms |
38092 KB |
Output is correct |
27 |
Correct |
735 ms |
38116 KB |
Output is correct |
28 |
Correct |
770 ms |
38112 KB |
Output is correct |
29 |
Correct |
707 ms |
37384 KB |
Output is correct |
30 |
Correct |
540 ms |
5336 KB |
Output is correct |
31 |
Correct |
708 ms |
38004 KB |
Output is correct |
32 |
Correct |
733 ms |
35976 KB |
Output is correct |
33 |
Correct |
525 ms |
5040 KB |
Output is correct |
34 |
Correct |
820 ms |
38036 KB |
Output is correct |
35 |
Correct |
713 ms |
32220 KB |
Output is correct |
36 |
Correct |
544 ms |
5096 KB |
Output is correct |
37 |
Correct |
557 ms |
5024 KB |
Output is correct |
38 |
Correct |
749 ms |
38008 KB |
Output is correct |
39 |
Correct |
622 ms |
38088 KB |
Output is correct |
40 |
Correct |
680 ms |
24408 KB |
Output is correct |
41 |
Correct |
881 ms |
38228 KB |
Output is correct |
42 |
Correct |
531 ms |
37960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
740 KB |
Output is correct |
2 |
Correct |
452 ms |
864 KB |
Output is correct |
3 |
Correct |
441 ms |
836 KB |
Output is correct |
4 |
Correct |
445 ms |
864 KB |
Output is correct |
5 |
Correct |
442 ms |
2336 KB |
Output is correct |
6 |
Correct |
429 ms |
2260 KB |
Output is correct |
7 |
Correct |
445 ms |
2280 KB |
Output is correct |
8 |
Correct |
459 ms |
2332 KB |
Output is correct |
9 |
Correct |
460 ms |
2552 KB |
Output is correct |
10 |
Correct |
458 ms |
2468 KB |
Output is correct |
11 |
Correct |
450 ms |
2352 KB |
Output is correct |
12 |
Correct |
452 ms |
2424 KB |
Output is correct |
13 |
Correct |
466 ms |
2340 KB |
Output is correct |
14 |
Correct |
451 ms |
2412 KB |
Output is correct |
15 |
Correct |
445 ms |
2496 KB |
Output is correct |
16 |
Correct |
445 ms |
2444 KB |
Output is correct |
17 |
Correct |
446 ms |
2316 KB |
Output is correct |
18 |
Correct |
470 ms |
2300 KB |
Output is correct |
19 |
Correct |
548 ms |
2456 KB |
Output is correct |
20 |
Correct |
521 ms |
2216 KB |
Output is correct |
21 |
Correct |
491 ms |
2512 KB |
Output is correct |
22 |
Correct |
459 ms |
2192 KB |
Output is correct |
23 |
Correct |
528 ms |
2332 KB |
Output is correct |
24 |
Correct |
505 ms |
2328 KB |
Output is correct |
25 |
Correct |
482 ms |
2380 KB |
Output is correct |
26 |
Correct |
461 ms |
2296 KB |
Output is correct |
27 |
Correct |
499 ms |
2388 KB |
Output is correct |
28 |
Correct |
449 ms |
2140 KB |
Output is correct |
29 |
Correct |
494 ms |
2416 KB |
Output is correct |
30 |
Correct |
462 ms |
2168 KB |
Output is correct |
31 |
Correct |
631 ms |
2368 KB |
Output is correct |
32 |
Correct |
603 ms |
2404 KB |
Output is correct |
33 |
Correct |
590 ms |
2508 KB |
Output is correct |
34 |
Correct |
572 ms |
2168 KB |
Output is correct |
35 |
Correct |
527 ms |
2352 KB |
Output is correct |
36 |
Correct |
539 ms |
2364 KB |
Output is correct |
37 |
Correct |
532 ms |
2380 KB |
Output is correct |
38 |
Correct |
526 ms |
2412 KB |
Output is correct |
39 |
Correct |
525 ms |
2344 KB |
Output is correct |
40 |
Correct |
531 ms |
2380 KB |
Output is correct |
41 |
Correct |
530 ms |
2384 KB |
Output is correct |
42 |
Correct |
532 ms |
2384 KB |
Output is correct |
43 |
Correct |
586 ms |
2308 KB |
Output is correct |
44 |
Correct |
602 ms |
2364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
415 ms |
740 KB |
Output is correct |
2 |
Correct |
452 ms |
864 KB |
Output is correct |
3 |
Correct |
441 ms |
836 KB |
Output is correct |
4 |
Correct |
445 ms |
864 KB |
Output is correct |
5 |
Correct |
442 ms |
2336 KB |
Output is correct |
6 |
Correct |
429 ms |
2260 KB |
Output is correct |
7 |
Correct |
445 ms |
2280 KB |
Output is correct |
8 |
Correct |
459 ms |
2332 KB |
Output is correct |
9 |
Correct |
460 ms |
2552 KB |
Output is correct |
10 |
Correct |
458 ms |
2468 KB |
Output is correct |
11 |
Correct |
450 ms |
2352 KB |
Output is correct |
12 |
Correct |
452 ms |
2424 KB |
Output is correct |
13 |
Correct |
466 ms |
2340 KB |
Output is correct |
14 |
Correct |
451 ms |
2412 KB |
Output is correct |
15 |
Correct |
445 ms |
2496 KB |
Output is correct |
16 |
Correct |
445 ms |
2444 KB |
Output is correct |
17 |
Correct |
446 ms |
2316 KB |
Output is correct |
18 |
Correct |
470 ms |
2300 KB |
Output is correct |
19 |
Correct |
843 ms |
38264 KB |
Output is correct |
20 |
Correct |
724 ms |
37976 KB |
Output is correct |
21 |
Correct |
678 ms |
36576 KB |
Output is correct |
22 |
Correct |
671 ms |
34336 KB |
Output is correct |
23 |
Correct |
525 ms |
5204 KB |
Output is correct |
24 |
Correct |
565 ms |
5120 KB |
Output is correct |
25 |
Correct |
745 ms |
38052 KB |
Output is correct |
26 |
Correct |
799 ms |
38092 KB |
Output is correct |
27 |
Correct |
735 ms |
38116 KB |
Output is correct |
28 |
Correct |
770 ms |
38112 KB |
Output is correct |
29 |
Correct |
707 ms |
37384 KB |
Output is correct |
30 |
Correct |
540 ms |
5336 KB |
Output is correct |
31 |
Correct |
708 ms |
38004 KB |
Output is correct |
32 |
Correct |
733 ms |
35976 KB |
Output is correct |
33 |
Correct |
525 ms |
5040 KB |
Output is correct |
34 |
Correct |
820 ms |
38036 KB |
Output is correct |
35 |
Correct |
713 ms |
32220 KB |
Output is correct |
36 |
Correct |
544 ms |
5096 KB |
Output is correct |
37 |
Correct |
557 ms |
5024 KB |
Output is correct |
38 |
Correct |
749 ms |
38008 KB |
Output is correct |
39 |
Correct |
622 ms |
38088 KB |
Output is correct |
40 |
Correct |
680 ms |
24408 KB |
Output is correct |
41 |
Correct |
881 ms |
38228 KB |
Output is correct |
42 |
Correct |
531 ms |
37960 KB |
Output is correct |
43 |
Correct |
548 ms |
2456 KB |
Output is correct |
44 |
Correct |
521 ms |
2216 KB |
Output is correct |
45 |
Correct |
491 ms |
2512 KB |
Output is correct |
46 |
Correct |
459 ms |
2192 KB |
Output is correct |
47 |
Correct |
528 ms |
2332 KB |
Output is correct |
48 |
Correct |
505 ms |
2328 KB |
Output is correct |
49 |
Correct |
482 ms |
2380 KB |
Output is correct |
50 |
Correct |
461 ms |
2296 KB |
Output is correct |
51 |
Correct |
499 ms |
2388 KB |
Output is correct |
52 |
Correct |
449 ms |
2140 KB |
Output is correct |
53 |
Correct |
494 ms |
2416 KB |
Output is correct |
54 |
Correct |
462 ms |
2168 KB |
Output is correct |
55 |
Correct |
631 ms |
2368 KB |
Output is correct |
56 |
Correct |
603 ms |
2404 KB |
Output is correct |
57 |
Correct |
590 ms |
2508 KB |
Output is correct |
58 |
Correct |
572 ms |
2168 KB |
Output is correct |
59 |
Correct |
527 ms |
2352 KB |
Output is correct |
60 |
Correct |
539 ms |
2364 KB |
Output is correct |
61 |
Correct |
532 ms |
2380 KB |
Output is correct |
62 |
Correct |
526 ms |
2412 KB |
Output is correct |
63 |
Correct |
525 ms |
2344 KB |
Output is correct |
64 |
Correct |
531 ms |
2380 KB |
Output is correct |
65 |
Correct |
530 ms |
2384 KB |
Output is correct |
66 |
Correct |
532 ms |
2384 KB |
Output is correct |
67 |
Correct |
586 ms |
2308 KB |
Output is correct |
68 |
Correct |
602 ms |
2364 KB |
Output is correct |
69 |
Correct |
2007 ms |
29220 KB |
Output is correct |
70 |
Correct |
1921 ms |
31944 KB |
Output is correct |
71 |
Correct |
634 ms |
4560 KB |
Output is correct |
72 |
Correct |
629 ms |
4664 KB |
Output is correct |
73 |
Correct |
665 ms |
4692 KB |
Output is correct |
74 |
Correct |
820 ms |
26908 KB |
Output is correct |
75 |
Correct |
640 ms |
4520 KB |
Output is correct |
76 |
Correct |
961 ms |
39168 KB |
Output is correct |
77 |
Correct |
902 ms |
26984 KB |
Output is correct |
78 |
Correct |
655 ms |
4648 KB |
Output is correct |
79 |
Correct |
640 ms |
4652 KB |
Output is correct |
80 |
Correct |
1225 ms |
20448 KB |
Output is correct |
81 |
Correct |
868 ms |
4764 KB |
Output is correct |
82 |
Correct |
1479 ms |
31844 KB |
Output is correct |
83 |
Correct |
1424 ms |
30860 KB |
Output is correct |
84 |
Correct |
901 ms |
4764 KB |
Output is correct |
85 |
Correct |
858 ms |
4708 KB |
Output is correct |
86 |
Correct |
1323 ms |
25672 KB |
Output is correct |
87 |
Correct |
1500 ms |
32052 KB |
Output is correct |
88 |
Correct |
923 ms |
4816 KB |
Output is correct |
89 |
Correct |
1306 ms |
30072 KB |
Output is correct |
90 |
Correct |
1487 ms |
31856 KB |
Output is correct |
91 |
Correct |
977 ms |
4732 KB |
Output is correct |
92 |
Correct |
1205 ms |
27912 KB |
Output is correct |
93 |
Correct |
889 ms |
4812 KB |
Output is correct |
94 |
Correct |
862 ms |
4668 KB |
Output is correct |
95 |
Correct |
908 ms |
4692 KB |
Output is correct |
96 |
Correct |
752 ms |
37940 KB |
Output is correct |
97 |
Correct |
1069 ms |
38172 KB |
Output is correct |
98 |
Correct |
1272 ms |
19848 KB |
Output is correct |
99 |
Correct |
3294 ms |
32028 KB |
Output is correct |
100 |
Correct |
1256 ms |
31168 KB |
Output is correct |