#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 2e5 + 10;
constexpr int mod = 1000000007;
char s[3][maxn], base[maxn];
int val[maxn];
int comb(array<int,3> a, array<int,3> b) { return (a[0]*b[0] + a[1]*b[1] + a[2]*b[2])%3; }
vector<array<int,3>> bases = {{0, 0, 1}, {0, 1, 0}, {0, 2, 2}, {1, 0, 0}, {1, 1, 2}, {1, 2, 1}, {2, 0, 2}, {2, 1, 1}, {2, 2, 0}};
int tipo(char c) { return c == 'J' ? 0 : c == 'O' ? 1 : 2; }
int pot[] = {1, 3, 9};
int aceita(int msk, int fim) {
array<int,3> aq = {msk%3, (msk/3)%3, (msk/9)%3};
int eu = 0;
for(int i = 0; i < 9; i++)
if(comb(aq, bases[i]) == fim) eu |= 1<<i;
return eu;
}
int cnt[27][3];
struct SegmentTree
{
struct Node {
int cor, qtd[27];
Node& operator%(const Node& a) {
static Node ret;
if(cor == a.cor) ret.cor = cor;
else ret.cor = -1;
for(int i = 0; i < 27; i++)
ret.qtd[i] = qtd[i] + a.qtd[i];
return ret;
}
int operator+(const Node& a) {
if(cor == a.cor) return cor;
return -1;
}
void rmv() {
for(int i = 0; i < 27; i++)
cnt[i][cor] -= qtd[i];
}
void add() {
for(int i = 0; i < 27; i++)
cnt[i][cor] += qtd[i];
}
} tree[4*maxn];
int a[maxn];
void build(int node, int i, int j) {
if(i == j) return (void)(tree[node].cor = a[i], tree[node].qtd[val[i]] = 1);
int m = (i+j) >> 1;
build(node<<1, i, m); build(node<<1|1, m+1, j);
tree[node] = tree[node<<1] % tree[node<<1|1];
}
void upd(int node, int i, int j, int l, int r, int c) {
if(i > r || j < l) return;
if(i >= l && j <= r && tree[node].cor != -1) {
if(c == tree[node].cor) return;
tree[node].rmv();
tree[node].cor = c;
tree[node].add();
return;
}
int m = (i+j) >> 1;
if(tree[node].cor != -1)
tree[node<<1|1].cor = tree[node<<1].cor = tree[node].cor;
upd(node<<1, i, m, l, r, c);
upd(node<<1|1, m+1, j, l, r, c);
tree[node].cor = tree[node<<1] + tree[node<<1|1];
}
} seg;
void check() {
int pode = (1 << 10) - 1;
for(int i = 0; i < 27 && pode; i++)
for(int j = 0; j < 3; j++)
if(cnt[i][j]) pode &= aceita(i, j);
puts(pode ? "Yes" : "No");
}
int main() {
int n; scanf("%d", &n);
for(int i = 0; i < 3; i++)
scanf(" %s", s[i]);
for(int i = 0; i < n; i++) {
for(int j = 0; j < 3; j++) {
val[i] += tipo(s[j][i]) * pot[j];
}
}
int q; scanf("%d", &q);
scanf(" %s", base);
for(int i = 0; i < n; i++)
++cnt[val[i]][tipo(base[i])], seg.a[i] = tipo(base[i]);
seg.build(1, 0, n-1);
check();
while(q--) {
int l, r; char c; scanf("%d %d %c", &l, &r, &c);
--l, --r;
seg.upd(1, 0, n-1, l, r, tipo(c));
check();
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | int n; scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf(" %s", s[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf(" %s", base);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:107:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | int l, r; char c; scanf("%d %d %c", &l, &r, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
217 ms |
2380 KB |
Output is correct |
2 |
Correct |
254 ms |
2476 KB |
Output is correct |
3 |
Correct |
273 ms |
2232 KB |
Output is correct |
4 |
Correct |
214 ms |
2336 KB |
Output is correct |
5 |
Correct |
206 ms |
2312 KB |
Output is correct |
6 |
Correct |
234 ms |
2268 KB |
Output is correct |
7 |
Correct |
204 ms |
2372 KB |
Output is correct |
8 |
Correct |
225 ms |
2460 KB |
Output is correct |
9 |
Correct |
230 ms |
2484 KB |
Output is correct |
10 |
Correct |
221 ms |
2532 KB |
Output is correct |
11 |
Correct |
219 ms |
2444 KB |
Output is correct |
12 |
Correct |
221 ms |
2472 KB |
Output is correct |
13 |
Correct |
220 ms |
2544 KB |
Output is correct |
14 |
Correct |
218 ms |
2560 KB |
Output is correct |
15 |
Correct |
218 ms |
2748 KB |
Output is correct |
16 |
Correct |
218 ms |
2352 KB |
Output is correct |
17 |
Correct |
233 ms |
2456 KB |
Output is correct |
18 |
Correct |
267 ms |
2408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
217 ms |
2380 KB |
Output is correct |
2 |
Correct |
254 ms |
2476 KB |
Output is correct |
3 |
Correct |
273 ms |
2232 KB |
Output is correct |
4 |
Correct |
214 ms |
2336 KB |
Output is correct |
5 |
Correct |
206 ms |
2312 KB |
Output is correct |
6 |
Correct |
234 ms |
2268 KB |
Output is correct |
7 |
Correct |
204 ms |
2372 KB |
Output is correct |
8 |
Correct |
225 ms |
2460 KB |
Output is correct |
9 |
Correct |
230 ms |
2484 KB |
Output is correct |
10 |
Correct |
221 ms |
2532 KB |
Output is correct |
11 |
Correct |
219 ms |
2444 KB |
Output is correct |
12 |
Correct |
221 ms |
2472 KB |
Output is correct |
13 |
Correct |
220 ms |
2544 KB |
Output is correct |
14 |
Correct |
218 ms |
2560 KB |
Output is correct |
15 |
Correct |
218 ms |
2748 KB |
Output is correct |
16 |
Correct |
218 ms |
2352 KB |
Output is correct |
17 |
Correct |
233 ms |
2456 KB |
Output is correct |
18 |
Correct |
267 ms |
2408 KB |
Output is correct |
19 |
Correct |
1087 ms |
64328 KB |
Output is correct |
20 |
Correct |
1141 ms |
64288 KB |
Output is correct |
21 |
Correct |
492 ms |
63928 KB |
Output is correct |
22 |
Correct |
533 ms |
63612 KB |
Output is correct |
23 |
Correct |
341 ms |
6868 KB |
Output is correct |
24 |
Correct |
323 ms |
6984 KB |
Output is correct |
25 |
Correct |
494 ms |
64308 KB |
Output is correct |
26 |
Correct |
605 ms |
64324 KB |
Output is correct |
27 |
Correct |
932 ms |
64396 KB |
Output is correct |
28 |
Correct |
816 ms |
64324 KB |
Output is correct |
29 |
Correct |
802 ms |
64180 KB |
Output is correct |
30 |
Correct |
529 ms |
6888 KB |
Output is correct |
31 |
Correct |
824 ms |
64300 KB |
Output is correct |
32 |
Correct |
731 ms |
64020 KB |
Output is correct |
33 |
Correct |
353 ms |
6916 KB |
Output is correct |
34 |
Correct |
748 ms |
64468 KB |
Output is correct |
35 |
Correct |
438 ms |
63172 KB |
Output is correct |
36 |
Correct |
319 ms |
7004 KB |
Output is correct |
37 |
Correct |
330 ms |
6896 KB |
Output is correct |
38 |
Correct |
1033 ms |
64120 KB |
Output is correct |
39 |
Correct |
259 ms |
64348 KB |
Output is correct |
40 |
Correct |
469 ms |
34448 KB |
Output is correct |
41 |
Correct |
378 ms |
64476 KB |
Output is correct |
42 |
Correct |
161 ms |
63792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
217 ms |
2380 KB |
Output is correct |
2 |
Correct |
254 ms |
2476 KB |
Output is correct |
3 |
Correct |
273 ms |
2232 KB |
Output is correct |
4 |
Correct |
214 ms |
2336 KB |
Output is correct |
5 |
Correct |
206 ms |
2312 KB |
Output is correct |
6 |
Correct |
234 ms |
2268 KB |
Output is correct |
7 |
Correct |
204 ms |
2372 KB |
Output is correct |
8 |
Correct |
225 ms |
2460 KB |
Output is correct |
9 |
Correct |
230 ms |
2484 KB |
Output is correct |
10 |
Correct |
221 ms |
2532 KB |
Output is correct |
11 |
Correct |
219 ms |
2444 KB |
Output is correct |
12 |
Correct |
221 ms |
2472 KB |
Output is correct |
13 |
Correct |
220 ms |
2544 KB |
Output is correct |
14 |
Correct |
218 ms |
2560 KB |
Output is correct |
15 |
Correct |
218 ms |
2748 KB |
Output is correct |
16 |
Correct |
218 ms |
2352 KB |
Output is correct |
17 |
Correct |
233 ms |
2456 KB |
Output is correct |
18 |
Correct |
267 ms |
2408 KB |
Output is correct |
19 |
Correct |
242 ms |
2420 KB |
Output is correct |
20 |
Correct |
277 ms |
2340 KB |
Output is correct |
21 |
Correct |
219 ms |
2472 KB |
Output is correct |
22 |
Correct |
190 ms |
2228 KB |
Output is correct |
23 |
Correct |
220 ms |
2532 KB |
Output is correct |
24 |
Correct |
204 ms |
2356 KB |
Output is correct |
25 |
Correct |
232 ms |
2440 KB |
Output is correct |
26 |
Correct |
197 ms |
2424 KB |
Output is correct |
27 |
Correct |
220 ms |
2376 KB |
Output is correct |
28 |
Correct |
210 ms |
2244 KB |
Output is correct |
29 |
Correct |
226 ms |
2416 KB |
Output is correct |
30 |
Correct |
194 ms |
2244 KB |
Output is correct |
31 |
Correct |
238 ms |
2476 KB |
Output is correct |
32 |
Correct |
223 ms |
2372 KB |
Output is correct |
33 |
Correct |
223 ms |
2476 KB |
Output is correct |
34 |
Correct |
201 ms |
2244 KB |
Output is correct |
35 |
Correct |
218 ms |
2544 KB |
Output is correct |
36 |
Correct |
215 ms |
2500 KB |
Output is correct |
37 |
Correct |
224 ms |
2424 KB |
Output is correct |
38 |
Correct |
219 ms |
2372 KB |
Output is correct |
39 |
Correct |
217 ms |
2500 KB |
Output is correct |
40 |
Correct |
216 ms |
2440 KB |
Output is correct |
41 |
Correct |
216 ms |
2388 KB |
Output is correct |
42 |
Correct |
216 ms |
2372 KB |
Output is correct |
43 |
Correct |
208 ms |
2292 KB |
Output is correct |
44 |
Correct |
219 ms |
2436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
217 ms |
2380 KB |
Output is correct |
2 |
Correct |
254 ms |
2476 KB |
Output is correct |
3 |
Correct |
273 ms |
2232 KB |
Output is correct |
4 |
Correct |
214 ms |
2336 KB |
Output is correct |
5 |
Correct |
206 ms |
2312 KB |
Output is correct |
6 |
Correct |
234 ms |
2268 KB |
Output is correct |
7 |
Correct |
204 ms |
2372 KB |
Output is correct |
8 |
Correct |
225 ms |
2460 KB |
Output is correct |
9 |
Correct |
230 ms |
2484 KB |
Output is correct |
10 |
Correct |
221 ms |
2532 KB |
Output is correct |
11 |
Correct |
219 ms |
2444 KB |
Output is correct |
12 |
Correct |
221 ms |
2472 KB |
Output is correct |
13 |
Correct |
220 ms |
2544 KB |
Output is correct |
14 |
Correct |
218 ms |
2560 KB |
Output is correct |
15 |
Correct |
218 ms |
2748 KB |
Output is correct |
16 |
Correct |
218 ms |
2352 KB |
Output is correct |
17 |
Correct |
233 ms |
2456 KB |
Output is correct |
18 |
Correct |
267 ms |
2408 KB |
Output is correct |
19 |
Correct |
1087 ms |
64328 KB |
Output is correct |
20 |
Correct |
1141 ms |
64288 KB |
Output is correct |
21 |
Correct |
492 ms |
63928 KB |
Output is correct |
22 |
Correct |
533 ms |
63612 KB |
Output is correct |
23 |
Correct |
341 ms |
6868 KB |
Output is correct |
24 |
Correct |
323 ms |
6984 KB |
Output is correct |
25 |
Correct |
494 ms |
64308 KB |
Output is correct |
26 |
Correct |
605 ms |
64324 KB |
Output is correct |
27 |
Correct |
932 ms |
64396 KB |
Output is correct |
28 |
Correct |
816 ms |
64324 KB |
Output is correct |
29 |
Correct |
802 ms |
64180 KB |
Output is correct |
30 |
Correct |
529 ms |
6888 KB |
Output is correct |
31 |
Correct |
824 ms |
64300 KB |
Output is correct |
32 |
Correct |
731 ms |
64020 KB |
Output is correct |
33 |
Correct |
353 ms |
6916 KB |
Output is correct |
34 |
Correct |
748 ms |
64468 KB |
Output is correct |
35 |
Correct |
438 ms |
63172 KB |
Output is correct |
36 |
Correct |
319 ms |
7004 KB |
Output is correct |
37 |
Correct |
330 ms |
6896 KB |
Output is correct |
38 |
Correct |
1033 ms |
64120 KB |
Output is correct |
39 |
Correct |
259 ms |
64348 KB |
Output is correct |
40 |
Correct |
469 ms |
34448 KB |
Output is correct |
41 |
Correct |
378 ms |
64476 KB |
Output is correct |
42 |
Correct |
161 ms |
63792 KB |
Output is correct |
43 |
Correct |
242 ms |
2420 KB |
Output is correct |
44 |
Correct |
277 ms |
2340 KB |
Output is correct |
45 |
Correct |
219 ms |
2472 KB |
Output is correct |
46 |
Correct |
190 ms |
2228 KB |
Output is correct |
47 |
Correct |
220 ms |
2532 KB |
Output is correct |
48 |
Correct |
204 ms |
2356 KB |
Output is correct |
49 |
Correct |
232 ms |
2440 KB |
Output is correct |
50 |
Correct |
197 ms |
2424 KB |
Output is correct |
51 |
Correct |
220 ms |
2376 KB |
Output is correct |
52 |
Correct |
210 ms |
2244 KB |
Output is correct |
53 |
Correct |
226 ms |
2416 KB |
Output is correct |
54 |
Correct |
194 ms |
2244 KB |
Output is correct |
55 |
Correct |
238 ms |
2476 KB |
Output is correct |
56 |
Correct |
223 ms |
2372 KB |
Output is correct |
57 |
Correct |
223 ms |
2476 KB |
Output is correct |
58 |
Correct |
201 ms |
2244 KB |
Output is correct |
59 |
Correct |
218 ms |
2544 KB |
Output is correct |
60 |
Correct |
215 ms |
2500 KB |
Output is correct |
61 |
Correct |
224 ms |
2424 KB |
Output is correct |
62 |
Correct |
219 ms |
2372 KB |
Output is correct |
63 |
Correct |
217 ms |
2500 KB |
Output is correct |
64 |
Correct |
216 ms |
2440 KB |
Output is correct |
65 |
Correct |
216 ms |
2388 KB |
Output is correct |
66 |
Correct |
216 ms |
2372 KB |
Output is correct |
67 |
Correct |
208 ms |
2292 KB |
Output is correct |
68 |
Correct |
219 ms |
2436 KB |
Output is correct |
69 |
Correct |
965 ms |
63540 KB |
Output is correct |
70 |
Correct |
1162 ms |
64324 KB |
Output is correct |
71 |
Correct |
325 ms |
6976 KB |
Output is correct |
72 |
Correct |
318 ms |
6912 KB |
Output is correct |
73 |
Correct |
323 ms |
6936 KB |
Output is correct |
74 |
Correct |
488 ms |
63608 KB |
Output is correct |
75 |
Correct |
339 ms |
6856 KB |
Output is correct |
76 |
Correct |
518 ms |
64316 KB |
Output is correct |
77 |
Correct |
528 ms |
63796 KB |
Output is correct |
78 |
Correct |
315 ms |
6844 KB |
Output is correct |
79 |
Correct |
322 ms |
6960 KB |
Output is correct |
80 |
Correct |
487 ms |
63044 KB |
Output is correct |
81 |
Correct |
331 ms |
6980 KB |
Output is correct |
82 |
Correct |
524 ms |
64316 KB |
Output is correct |
83 |
Correct |
529 ms |
64028 KB |
Output is correct |
84 |
Correct |
325 ms |
7100 KB |
Output is correct |
85 |
Correct |
319 ms |
6948 KB |
Output is correct |
86 |
Correct |
804 ms |
63412 KB |
Output is correct |
87 |
Correct |
813 ms |
64348 KB |
Output is correct |
88 |
Correct |
412 ms |
6984 KB |
Output is correct |
89 |
Correct |
654 ms |
63648 KB |
Output is correct |
90 |
Correct |
693 ms |
64384 KB |
Output is correct |
91 |
Correct |
407 ms |
7000 KB |
Output is correct |
92 |
Correct |
455 ms |
63488 KB |
Output is correct |
93 |
Correct |
324 ms |
6940 KB |
Output is correct |
94 |
Correct |
319 ms |
6940 KB |
Output is correct |
95 |
Correct |
330 ms |
6956 KB |
Output is correct |
96 |
Correct |
980 ms |
64100 KB |
Output is correct |
97 |
Correct |
275 ms |
64324 KB |
Output is correct |
98 |
Correct |
448 ms |
34364 KB |
Output is correct |
99 |
Correct |
423 ms |
64556 KB |
Output is correct |
100 |
Correct |
213 ms |
63772 KB |
Output is correct |