#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Node {
public:
bool stequal = false;
bool jequal = false;
bool oequal = false;
bool iequal = false;
};
class IsEqual {
private:
vector<string> s;
string t;
int n;
vector<vector<Node>> tree;
vector<vector<char>> lazy;
void build(int v, int tl, int tr) {
if (tl == tr) {
for (int j = 0; j < 9; j++) {
tree[v][j].stequal = (s[j][tl] == t[tl]);
tree[v][j].jequal = (s[j][tl] == 'J');
tree[v][j].oequal = (s[j][tl] == 'O');
tree[v][j].iequal = (s[j][tl] == 'I');
}
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
for (int j = 0; j < 9; j++) {
tree[v][j].stequal = tree[2 * v][j].stequal & tree[2 * v + 1][j].stequal;
tree[v][j].jequal = tree[2 * v][j].jequal & tree[2 * v + 1][j].jequal;
tree[v][j].oequal = tree[2 * v][j].oequal & tree[2 * v + 1][j].oequal;
tree[v][j].iequal = tree[2 * v][j].iequal & tree[2 * v + 1][j].iequal;
}
}
}
void modify(int v, int tl, int tr, int l, int r, char ch) {
for (int j = 0; j < 9; j++) {
if (lazy[v][j] != 'X') {
if (lazy[v][j] == 'J') {
tree[v][j].stequal = tree[v][j].jequal;
} else {
if (lazy[v][j] == 'O') {
tree[v][j].stequal = tree[v][j].oequal;
} else {
tree[v][j].stequal = tree[v][j].iequal;
}
}
if (tl < tr) {
lazy[2 * v][j] = lazy[2 * v + 1][j] = lazy[v][j];
}
lazy[v][j] = 'X';
}
}
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
for (int j = 0; j < 9; j++) {
lazy[v][j] = ch;
if (lazy[v][j] == 'J') {
tree[v][j].stequal = tree[v][j].jequal;
} else {
if (lazy[v][j] == 'O') {
tree[v][j].stequal = tree[v][j].oequal;
} else {
tree[v][j].stequal = tree[v][j].iequal;
}
}
if (tl < tr) {
lazy[2 * v][j] = lazy[2 * v + 1][j] = lazy[v][j];
}
lazy[v][j] = 'X';
}
} else {
int tm = (tl + tr) / 2;
modify(2 * v, tl, tm, l, r, ch);
modify(2 * v + 1, tm + 1, tr, l, r, ch);
for (int j = 0; j < 9; j++) {
tree[v][j].stequal = tree[2 * v][j].stequal & tree[2 * v + 1][j].stequal;
}
}
}
public:
IsEqual(vector<string> s, string t) : s(s), t(t), n((int) t.size()), tree(4 * ((int) t.size() + 7), vector<Node> (9)), lazy(4 * ((int) t.size() + 7), vector<char> (9, 'X')) {
build(1, 0, n - 1);
}
void modify(int l, int r, char ch) {
l--;
r--;
modify(1, 0, n - 1, l, r, ch);
}
bool isEqual() {
bool ok = false;
for (int j = 0; j < 9; j++) {
ok |= tree[1][j].stequal;
}
return ok;
}
};
string operator + (string s, string t) {
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] != t[i]) {
int x = 'J' + 'O' + 'I' - s[i] - t[i];
s[i] = x;
}
}
return s;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
// freopen ("TonyStark", "r", stdin);
int n, q;
string a, b, c, t;
cin >> n >> a >> b >> c >> q >> t;
vector<string> strs;
strs.push_back(a);
strs.push_back(b);
strs.push_back(c);
strs.push_back(a + b);
strs.push_back(b + c);
strs.push_back(c + a);
strs.push_back(a + (b + c));
strs.push_back(b + (c + a));
strs.push_back(c + (a + b));
IsEqual all(strs, t);
function <string()> solve = [&] () {
if (all.isEqual()) {
return "Yes";
} else {
return "No";
}
};
cout << solve() << "\n";
while (q--) {
int l, r;
string ch;
cin >> l >> r >> ch;
all.modify(l, r, ch[0]);
cout << solve() << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
908 KB |
Output is correct |
2 |
Correct |
340 ms |
896 KB |
Output is correct |
3 |
Correct |
465 ms |
932 KB |
Output is correct |
4 |
Correct |
215 ms |
964 KB |
Output is correct |
5 |
Correct |
206 ms |
872 KB |
Output is correct |
6 |
Correct |
221 ms |
912 KB |
Output is correct |
7 |
Correct |
215 ms |
900 KB |
Output is correct |
8 |
Correct |
232 ms |
944 KB |
Output is correct |
9 |
Correct |
233 ms |
952 KB |
Output is correct |
10 |
Correct |
228 ms |
844 KB |
Output is correct |
11 |
Correct |
242 ms |
1068 KB |
Output is correct |
12 |
Correct |
232 ms |
872 KB |
Output is correct |
13 |
Correct |
249 ms |
940 KB |
Output is correct |
14 |
Correct |
241 ms |
968 KB |
Output is correct |
15 |
Correct |
243 ms |
940 KB |
Output is correct |
16 |
Correct |
222 ms |
924 KB |
Output is correct |
17 |
Correct |
237 ms |
876 KB |
Output is correct |
18 |
Correct |
476 ms |
1012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
908 KB |
Output is correct |
2 |
Correct |
340 ms |
896 KB |
Output is correct |
3 |
Correct |
465 ms |
932 KB |
Output is correct |
4 |
Correct |
215 ms |
964 KB |
Output is correct |
5 |
Correct |
206 ms |
872 KB |
Output is correct |
6 |
Correct |
221 ms |
912 KB |
Output is correct |
7 |
Correct |
215 ms |
900 KB |
Output is correct |
8 |
Correct |
232 ms |
944 KB |
Output is correct |
9 |
Correct |
233 ms |
952 KB |
Output is correct |
10 |
Correct |
228 ms |
844 KB |
Output is correct |
11 |
Correct |
242 ms |
1068 KB |
Output is correct |
12 |
Correct |
232 ms |
872 KB |
Output is correct |
13 |
Correct |
249 ms |
940 KB |
Output is correct |
14 |
Correct |
241 ms |
968 KB |
Output is correct |
15 |
Correct |
243 ms |
940 KB |
Output is correct |
16 |
Correct |
222 ms |
924 KB |
Output is correct |
17 |
Correct |
237 ms |
876 KB |
Output is correct |
18 |
Correct |
476 ms |
1012 KB |
Output is correct |
19 |
Correct |
2236 ms |
107524 KB |
Output is correct |
20 |
Correct |
2370 ms |
107568 KB |
Output is correct |
21 |
Correct |
841 ms |
101160 KB |
Output is correct |
22 |
Correct |
967 ms |
90892 KB |
Output is correct |
23 |
Correct |
402 ms |
6388 KB |
Output is correct |
24 |
Correct |
458 ms |
6540 KB |
Output is correct |
25 |
Correct |
969 ms |
107712 KB |
Output is correct |
26 |
Correct |
1100 ms |
107480 KB |
Output is correct |
27 |
Correct |
1341 ms |
107464 KB |
Output is correct |
28 |
Correct |
1415 ms |
107528 KB |
Output is correct |
29 |
Correct |
1187 ms |
104544 KB |
Output is correct |
30 |
Correct |
535 ms |
6492 KB |
Output is correct |
31 |
Correct |
1301 ms |
107824 KB |
Output is correct |
32 |
Correct |
1146 ms |
98136 KB |
Output is correct |
33 |
Correct |
449 ms |
6252 KB |
Output is correct |
34 |
Correct |
1276 ms |
107644 KB |
Output is correct |
35 |
Correct |
778 ms |
80232 KB |
Output is correct |
36 |
Correct |
416 ms |
6496 KB |
Output is correct |
37 |
Correct |
420 ms |
6276 KB |
Output is correct |
38 |
Correct |
2081 ms |
107652 KB |
Output is correct |
39 |
Correct |
428 ms |
107616 KB |
Output is correct |
40 |
Correct |
853 ms |
70968 KB |
Output is correct |
41 |
Correct |
2696 ms |
107728 KB |
Output is correct |
42 |
Correct |
208 ms |
107760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
908 KB |
Output is correct |
2 |
Correct |
340 ms |
896 KB |
Output is correct |
3 |
Correct |
465 ms |
932 KB |
Output is correct |
4 |
Correct |
215 ms |
964 KB |
Output is correct |
5 |
Correct |
206 ms |
872 KB |
Output is correct |
6 |
Correct |
221 ms |
912 KB |
Output is correct |
7 |
Correct |
215 ms |
900 KB |
Output is correct |
8 |
Correct |
232 ms |
944 KB |
Output is correct |
9 |
Correct |
233 ms |
952 KB |
Output is correct |
10 |
Correct |
228 ms |
844 KB |
Output is correct |
11 |
Correct |
242 ms |
1068 KB |
Output is correct |
12 |
Correct |
232 ms |
872 KB |
Output is correct |
13 |
Correct |
249 ms |
940 KB |
Output is correct |
14 |
Correct |
241 ms |
968 KB |
Output is correct |
15 |
Correct |
243 ms |
940 KB |
Output is correct |
16 |
Correct |
222 ms |
924 KB |
Output is correct |
17 |
Correct |
237 ms |
876 KB |
Output is correct |
18 |
Correct |
476 ms |
1012 KB |
Output is correct |
19 |
Correct |
334 ms |
1036 KB |
Output is correct |
20 |
Correct |
459 ms |
836 KB |
Output is correct |
21 |
Correct |
229 ms |
856 KB |
Output is correct |
22 |
Correct |
196 ms |
908 KB |
Output is correct |
23 |
Correct |
249 ms |
856 KB |
Output is correct |
24 |
Correct |
220 ms |
996 KB |
Output is correct |
25 |
Correct |
238 ms |
880 KB |
Output is correct |
26 |
Correct |
216 ms |
928 KB |
Output is correct |
27 |
Correct |
225 ms |
1016 KB |
Output is correct |
28 |
Correct |
200 ms |
888 KB |
Output is correct |
29 |
Correct |
238 ms |
924 KB |
Output is correct |
30 |
Correct |
198 ms |
836 KB |
Output is correct |
31 |
Correct |
219 ms |
956 KB |
Output is correct |
32 |
Correct |
217 ms |
1032 KB |
Output is correct |
33 |
Correct |
229 ms |
924 KB |
Output is correct |
34 |
Correct |
201 ms |
816 KB |
Output is correct |
35 |
Correct |
232 ms |
956 KB |
Output is correct |
36 |
Correct |
230 ms |
884 KB |
Output is correct |
37 |
Correct |
223 ms |
924 KB |
Output is correct |
38 |
Correct |
237 ms |
936 KB |
Output is correct |
39 |
Correct |
224 ms |
920 KB |
Output is correct |
40 |
Correct |
234 ms |
1124 KB |
Output is correct |
41 |
Correct |
226 ms |
852 KB |
Output is correct |
42 |
Correct |
230 ms |
1048 KB |
Output is correct |
43 |
Correct |
223 ms |
840 KB |
Output is correct |
44 |
Correct |
238 ms |
872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
908 KB |
Output is correct |
2 |
Correct |
340 ms |
896 KB |
Output is correct |
3 |
Correct |
465 ms |
932 KB |
Output is correct |
4 |
Correct |
215 ms |
964 KB |
Output is correct |
5 |
Correct |
206 ms |
872 KB |
Output is correct |
6 |
Correct |
221 ms |
912 KB |
Output is correct |
7 |
Correct |
215 ms |
900 KB |
Output is correct |
8 |
Correct |
232 ms |
944 KB |
Output is correct |
9 |
Correct |
233 ms |
952 KB |
Output is correct |
10 |
Correct |
228 ms |
844 KB |
Output is correct |
11 |
Correct |
242 ms |
1068 KB |
Output is correct |
12 |
Correct |
232 ms |
872 KB |
Output is correct |
13 |
Correct |
249 ms |
940 KB |
Output is correct |
14 |
Correct |
241 ms |
968 KB |
Output is correct |
15 |
Correct |
243 ms |
940 KB |
Output is correct |
16 |
Correct |
222 ms |
924 KB |
Output is correct |
17 |
Correct |
237 ms |
876 KB |
Output is correct |
18 |
Correct |
476 ms |
1012 KB |
Output is correct |
19 |
Correct |
2236 ms |
107524 KB |
Output is correct |
20 |
Correct |
2370 ms |
107568 KB |
Output is correct |
21 |
Correct |
841 ms |
101160 KB |
Output is correct |
22 |
Correct |
967 ms |
90892 KB |
Output is correct |
23 |
Correct |
402 ms |
6388 KB |
Output is correct |
24 |
Correct |
458 ms |
6540 KB |
Output is correct |
25 |
Correct |
969 ms |
107712 KB |
Output is correct |
26 |
Correct |
1100 ms |
107480 KB |
Output is correct |
27 |
Correct |
1341 ms |
107464 KB |
Output is correct |
28 |
Correct |
1415 ms |
107528 KB |
Output is correct |
29 |
Correct |
1187 ms |
104544 KB |
Output is correct |
30 |
Correct |
535 ms |
6492 KB |
Output is correct |
31 |
Correct |
1301 ms |
107824 KB |
Output is correct |
32 |
Correct |
1146 ms |
98136 KB |
Output is correct |
33 |
Correct |
449 ms |
6252 KB |
Output is correct |
34 |
Correct |
1276 ms |
107644 KB |
Output is correct |
35 |
Correct |
778 ms |
80232 KB |
Output is correct |
36 |
Correct |
416 ms |
6496 KB |
Output is correct |
37 |
Correct |
420 ms |
6276 KB |
Output is correct |
38 |
Correct |
2081 ms |
107652 KB |
Output is correct |
39 |
Correct |
428 ms |
107616 KB |
Output is correct |
40 |
Correct |
853 ms |
70968 KB |
Output is correct |
41 |
Correct |
2696 ms |
107728 KB |
Output is correct |
42 |
Correct |
208 ms |
107760 KB |
Output is correct |
43 |
Correct |
334 ms |
1036 KB |
Output is correct |
44 |
Correct |
459 ms |
836 KB |
Output is correct |
45 |
Correct |
229 ms |
856 KB |
Output is correct |
46 |
Correct |
196 ms |
908 KB |
Output is correct |
47 |
Correct |
249 ms |
856 KB |
Output is correct |
48 |
Correct |
220 ms |
996 KB |
Output is correct |
49 |
Correct |
238 ms |
880 KB |
Output is correct |
50 |
Correct |
216 ms |
928 KB |
Output is correct |
51 |
Correct |
225 ms |
1016 KB |
Output is correct |
52 |
Correct |
200 ms |
888 KB |
Output is correct |
53 |
Correct |
238 ms |
924 KB |
Output is correct |
54 |
Correct |
198 ms |
836 KB |
Output is correct |
55 |
Correct |
219 ms |
956 KB |
Output is correct |
56 |
Correct |
217 ms |
1032 KB |
Output is correct |
57 |
Correct |
229 ms |
924 KB |
Output is correct |
58 |
Correct |
201 ms |
816 KB |
Output is correct |
59 |
Correct |
232 ms |
956 KB |
Output is correct |
60 |
Correct |
230 ms |
884 KB |
Output is correct |
61 |
Correct |
223 ms |
924 KB |
Output is correct |
62 |
Correct |
237 ms |
936 KB |
Output is correct |
63 |
Correct |
224 ms |
920 KB |
Output is correct |
64 |
Correct |
234 ms |
1124 KB |
Output is correct |
65 |
Correct |
226 ms |
852 KB |
Output is correct |
66 |
Correct |
230 ms |
1048 KB |
Output is correct |
67 |
Correct |
223 ms |
840 KB |
Output is correct |
68 |
Correct |
238 ms |
872 KB |
Output is correct |
69 |
Correct |
1863 ms |
90148 KB |
Output is correct |
70 |
Correct |
2318 ms |
107744 KB |
Output is correct |
71 |
Correct |
415 ms |
6316 KB |
Output is correct |
72 |
Correct |
393 ms |
6432 KB |
Output is correct |
73 |
Correct |
403 ms |
6624 KB |
Output is correct |
74 |
Correct |
854 ms |
89852 KB |
Output is correct |
75 |
Correct |
400 ms |
6292 KB |
Output is correct |
76 |
Correct |
890 ms |
107644 KB |
Output is correct |
77 |
Correct |
961 ms |
90140 KB |
Output is correct |
78 |
Correct |
390 ms |
6416 KB |
Output is correct |
79 |
Correct |
396 ms |
6408 KB |
Output is correct |
80 |
Correct |
848 ms |
77096 KB |
Output is correct |
81 |
Correct |
405 ms |
6192 KB |
Output is correct |
82 |
Correct |
926 ms |
107696 KB |
Output is correct |
83 |
Correct |
1030 ms |
101272 KB |
Output is correct |
84 |
Correct |
420 ms |
6264 KB |
Output is correct |
85 |
Correct |
414 ms |
6212 KB |
Output is correct |
86 |
Correct |
1319 ms |
81800 KB |
Output is correct |
87 |
Correct |
1400 ms |
107616 KB |
Output is correct |
88 |
Correct |
576 ms |
6344 KB |
Output is correct |
89 |
Correct |
1133 ms |
94856 KB |
Output is correct |
90 |
Correct |
1214 ms |
107572 KB |
Output is correct |
91 |
Correct |
532 ms |
6380 KB |
Output is correct |
92 |
Correct |
776 ms |
80600 KB |
Output is correct |
93 |
Correct |
389 ms |
6344 KB |
Output is correct |
94 |
Correct |
429 ms |
6244 KB |
Output is correct |
95 |
Correct |
415 ms |
6272 KB |
Output is correct |
96 |
Correct |
1980 ms |
107636 KB |
Output is correct |
97 |
Correct |
402 ms |
107508 KB |
Output is correct |
98 |
Correct |
802 ms |
70840 KB |
Output is correct |
99 |
Correct |
2572 ms |
107792 KB |
Output is correct |
100 |
Correct |
214 ms |
107680 KB |
Output is correct |