#include <bits/stdc++.h>
using namespace std;
int n, p;
char d;
vector<int> wl, wr;
vector<vector<int> > sg, lz;
vector<vector<vector<int> > > pf;
vector<int> x(vector<int> u, vector<int> v)
{
vector<int> an(n);
for (int i = 0; i < n; i++)
an[i] = (6 - u[i] - v[i]) % 3;
return an;
}
vector<int> ct()
{
vector<int> an(n);
for (int i = 0; i < n; i++)
{
cin >> d;
if (d == 'O')
an[i] = 0;
else if (d == 'I')
an[i] = 1;
else
an[i] = 2;
}
return an;
}
void push(int i, int j)
{
if (lz[i][j] == -1)
return;
sg[i][j] = pf[wr[i] - p][j][lz[i][j]] - pf[wl[i] - p][j][lz[i][j]];
if (i < p)
lz[2 * i][j] = lz[2 * i + 1][j] = lz[i][j];
lz[i][j] = -1;
return;
}
int qsum(int l, int r, int i, int j)
{
push(i, j);
if (wl[i] >= r || wr[i] <= l)
return 0;
if (wl[i] >= l && wr[i] <= r)
return sg[i][j];
return qsum(l, r, 2 * i, j) + qsum(l, r, 2 * i + 1, j);
}
void rset(int l, int r, int i, int j, int w)
{
push(i, j);
if (wl[i] >= r || wr[i] <= l)
return;
if (wl[i] >= l && wr[i] <= r)
{
lz[i][j] = w;
push(i, j);
return;
}
rset(l, r, 2 * i, j, w);
rset(l, r, 2 * i + 1, j, w);
sg[i][j] = sg[2 * i][j] + sg[2 * i + 1][j];
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int i, j, k, q, l, r;
bool z = false;
cin >> n;
vector<int> a = ct(), b = ct(), c = ct();
vector<vector<int> > pos = {a, b, c, x(b, c), x(c, a), x(a, b), x(a, x(b, c)), x(b, x(c, a)), x(c, x(a, b))};
p = n;
while (p != (p & -p))
p++;
pf.resize(p + 1);
for (i = 0; i <= p; i++)
{
pf[i].resize(9);
for (j = 0; j < 9; j++)
{
pf[i][j].resize(3);
for (k = 0; k < 3; k++)
{
if (i)
{
pf[i][j][k] = pf[i - 1][j][k];
if (i <= n && pos[j][i - 1] == k)
pf[i][j][k]++;
}
else
pf[i][j][k] = 0;
}
}
}
cin >> q;
vector<int> v = ct();
wl.resize(2 * p);
wr.resize(2 * p);
sg.resize(2 * p);
lz.resize(2 * p);
for (i = p; i < 2 * p; i++)
{
sg[i].resize(9);
lz[i].resize(9);
for (j = 0; j < 9; j++)
{
if (i < p + n && pos[j][i - p] == v[i - p])
sg[i][j] = 1;
else
sg[i][j] = 0;
lz[i][j] = -1;
}
wl[i] = i;
wr[i] = i + 1;
}
for (i = p - 1; i > 0; i--)
{
sg[i].resize(9);
lz[i].resize(9);
for (j = 0; j < 9; j++)
{
sg[i][j] = sg[2 * i][j] + sg[2 * i + 1][j];
lz[i][j] = -1;
}
wl[i] = wl[2 * i];
wr[i] = wr[2 * i + 1];
}
for (j = 0; j < 9; j++)
{
if (qsum(p, 2 * p, 1, j) == n)
z = true;
}
if (z)
cout << "Yes" << endl;
else
cout << "No" << endl;
while (q--)
{
cin >> l >> r >> d;
if (d == 'O')
k = 0;
else if (d == 'I')
k = 1;
else
k = 2;
z = false;
for (j = 0; j < 9; j++)
{
rset(p + l - 1, p + r, 1, j, k);
if (qsum(p, 2 * p, 1, j) == n)
z = true;
}
if (z)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
2488 KB |
Output is correct |
2 |
Correct |
565 ms |
2652 KB |
Output is correct |
3 |
Correct |
626 ms |
2520 KB |
Output is correct |
4 |
Correct |
521 ms |
2816 KB |
Output is correct |
5 |
Correct |
474 ms |
2664 KB |
Output is correct |
6 |
Correct |
474 ms |
2388 KB |
Output is correct |
7 |
Correct |
495 ms |
2564 KB |
Output is correct |
8 |
Correct |
493 ms |
2556 KB |
Output is correct |
9 |
Correct |
491 ms |
2640 KB |
Output is correct |
10 |
Correct |
523 ms |
2492 KB |
Output is correct |
11 |
Correct |
539 ms |
2644 KB |
Output is correct |
12 |
Correct |
496 ms |
2456 KB |
Output is correct |
13 |
Correct |
501 ms |
2852 KB |
Output is correct |
14 |
Correct |
499 ms |
2616 KB |
Output is correct |
15 |
Correct |
520 ms |
2640 KB |
Output is correct |
16 |
Correct |
507 ms |
2540 KB |
Output is correct |
17 |
Correct |
505 ms |
2640 KB |
Output is correct |
18 |
Correct |
598 ms |
2552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
2488 KB |
Output is correct |
2 |
Correct |
565 ms |
2652 KB |
Output is correct |
3 |
Correct |
626 ms |
2520 KB |
Output is correct |
4 |
Correct |
521 ms |
2816 KB |
Output is correct |
5 |
Correct |
474 ms |
2664 KB |
Output is correct |
6 |
Correct |
474 ms |
2388 KB |
Output is correct |
7 |
Correct |
495 ms |
2564 KB |
Output is correct |
8 |
Correct |
493 ms |
2556 KB |
Output is correct |
9 |
Correct |
491 ms |
2640 KB |
Output is correct |
10 |
Correct |
523 ms |
2492 KB |
Output is correct |
11 |
Correct |
539 ms |
2644 KB |
Output is correct |
12 |
Correct |
496 ms |
2456 KB |
Output is correct |
13 |
Correct |
501 ms |
2852 KB |
Output is correct |
14 |
Correct |
499 ms |
2616 KB |
Output is correct |
15 |
Correct |
520 ms |
2640 KB |
Output is correct |
16 |
Correct |
507 ms |
2540 KB |
Output is correct |
17 |
Correct |
505 ms |
2640 KB |
Output is correct |
18 |
Correct |
598 ms |
2552 KB |
Output is correct |
19 |
Correct |
3065 ms |
231412 KB |
Output is correct |
20 |
Correct |
3008 ms |
230156 KB |
Output is correct |
21 |
Correct |
1432 ms |
229548 KB |
Output is correct |
22 |
Correct |
1614 ms |
228292 KB |
Output is correct |
23 |
Correct |
905 ms |
17364 KB |
Output is correct |
24 |
Correct |
836 ms |
17320 KB |
Output is correct |
25 |
Correct |
1585 ms |
230360 KB |
Output is correct |
26 |
Correct |
1714 ms |
230200 KB |
Output is correct |
27 |
Correct |
2111 ms |
230660 KB |
Output is correct |
28 |
Correct |
2141 ms |
230400 KB |
Output is correct |
29 |
Correct |
1967 ms |
230396 KB |
Output is correct |
30 |
Correct |
952 ms |
17212 KB |
Output is correct |
31 |
Correct |
2158 ms |
230396 KB |
Output is correct |
32 |
Correct |
2103 ms |
229320 KB |
Output is correct |
33 |
Correct |
972 ms |
17144 KB |
Output is correct |
34 |
Correct |
2141 ms |
230344 KB |
Output is correct |
35 |
Correct |
1477 ms |
227136 KB |
Output is correct |
36 |
Correct |
856 ms |
17140 KB |
Output is correct |
37 |
Correct |
813 ms |
17380 KB |
Output is correct |
38 |
Correct |
2658 ms |
230000 KB |
Output is correct |
39 |
Correct |
941 ms |
230496 KB |
Output is correct |
40 |
Correct |
1401 ms |
118964 KB |
Output is correct |
41 |
Correct |
3532 ms |
230472 KB |
Output is correct |
42 |
Correct |
820 ms |
230012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
2488 KB |
Output is correct |
2 |
Correct |
565 ms |
2652 KB |
Output is correct |
3 |
Correct |
626 ms |
2520 KB |
Output is correct |
4 |
Correct |
521 ms |
2816 KB |
Output is correct |
5 |
Correct |
474 ms |
2664 KB |
Output is correct |
6 |
Correct |
474 ms |
2388 KB |
Output is correct |
7 |
Correct |
495 ms |
2564 KB |
Output is correct |
8 |
Correct |
493 ms |
2556 KB |
Output is correct |
9 |
Correct |
491 ms |
2640 KB |
Output is correct |
10 |
Correct |
523 ms |
2492 KB |
Output is correct |
11 |
Correct |
539 ms |
2644 KB |
Output is correct |
12 |
Correct |
496 ms |
2456 KB |
Output is correct |
13 |
Correct |
501 ms |
2852 KB |
Output is correct |
14 |
Correct |
499 ms |
2616 KB |
Output is correct |
15 |
Correct |
520 ms |
2640 KB |
Output is correct |
16 |
Correct |
507 ms |
2540 KB |
Output is correct |
17 |
Correct |
505 ms |
2640 KB |
Output is correct |
18 |
Correct |
598 ms |
2552 KB |
Output is correct |
19 |
Correct |
573 ms |
2516 KB |
Output is correct |
20 |
Correct |
636 ms |
2384 KB |
Output is correct |
21 |
Correct |
531 ms |
2660 KB |
Output is correct |
22 |
Correct |
469 ms |
2444 KB |
Output is correct |
23 |
Correct |
517 ms |
2436 KB |
Output is correct |
24 |
Correct |
524 ms |
2400 KB |
Output is correct |
25 |
Correct |
534 ms |
2676 KB |
Output is correct |
26 |
Correct |
476 ms |
2384 KB |
Output is correct |
27 |
Correct |
500 ms |
3060 KB |
Output is correct |
28 |
Correct |
450 ms |
2460 KB |
Output is correct |
29 |
Correct |
510 ms |
2572 KB |
Output is correct |
30 |
Correct |
464 ms |
2644 KB |
Output is correct |
31 |
Correct |
490 ms |
2428 KB |
Output is correct |
32 |
Correct |
495 ms |
2636 KB |
Output is correct |
33 |
Correct |
497 ms |
2664 KB |
Output is correct |
34 |
Correct |
462 ms |
2388 KB |
Output is correct |
35 |
Correct |
500 ms |
2484 KB |
Output is correct |
36 |
Correct |
498 ms |
2640 KB |
Output is correct |
37 |
Correct |
496 ms |
2644 KB |
Output is correct |
38 |
Correct |
499 ms |
2584 KB |
Output is correct |
39 |
Correct |
496 ms |
2672 KB |
Output is correct |
40 |
Correct |
494 ms |
2588 KB |
Output is correct |
41 |
Correct |
505 ms |
2648 KB |
Output is correct |
42 |
Correct |
494 ms |
2676 KB |
Output is correct |
43 |
Correct |
481 ms |
2564 KB |
Output is correct |
44 |
Correct |
503 ms |
2612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
2488 KB |
Output is correct |
2 |
Correct |
565 ms |
2652 KB |
Output is correct |
3 |
Correct |
626 ms |
2520 KB |
Output is correct |
4 |
Correct |
521 ms |
2816 KB |
Output is correct |
5 |
Correct |
474 ms |
2664 KB |
Output is correct |
6 |
Correct |
474 ms |
2388 KB |
Output is correct |
7 |
Correct |
495 ms |
2564 KB |
Output is correct |
8 |
Correct |
493 ms |
2556 KB |
Output is correct |
9 |
Correct |
491 ms |
2640 KB |
Output is correct |
10 |
Correct |
523 ms |
2492 KB |
Output is correct |
11 |
Correct |
539 ms |
2644 KB |
Output is correct |
12 |
Correct |
496 ms |
2456 KB |
Output is correct |
13 |
Correct |
501 ms |
2852 KB |
Output is correct |
14 |
Correct |
499 ms |
2616 KB |
Output is correct |
15 |
Correct |
520 ms |
2640 KB |
Output is correct |
16 |
Correct |
507 ms |
2540 KB |
Output is correct |
17 |
Correct |
505 ms |
2640 KB |
Output is correct |
18 |
Correct |
598 ms |
2552 KB |
Output is correct |
19 |
Correct |
3065 ms |
231412 KB |
Output is correct |
20 |
Correct |
3008 ms |
230156 KB |
Output is correct |
21 |
Correct |
1432 ms |
229548 KB |
Output is correct |
22 |
Correct |
1614 ms |
228292 KB |
Output is correct |
23 |
Correct |
905 ms |
17364 KB |
Output is correct |
24 |
Correct |
836 ms |
17320 KB |
Output is correct |
25 |
Correct |
1585 ms |
230360 KB |
Output is correct |
26 |
Correct |
1714 ms |
230200 KB |
Output is correct |
27 |
Correct |
2111 ms |
230660 KB |
Output is correct |
28 |
Correct |
2141 ms |
230400 KB |
Output is correct |
29 |
Correct |
1967 ms |
230396 KB |
Output is correct |
30 |
Correct |
952 ms |
17212 KB |
Output is correct |
31 |
Correct |
2158 ms |
230396 KB |
Output is correct |
32 |
Correct |
2103 ms |
229320 KB |
Output is correct |
33 |
Correct |
972 ms |
17144 KB |
Output is correct |
34 |
Correct |
2141 ms |
230344 KB |
Output is correct |
35 |
Correct |
1477 ms |
227136 KB |
Output is correct |
36 |
Correct |
856 ms |
17140 KB |
Output is correct |
37 |
Correct |
813 ms |
17380 KB |
Output is correct |
38 |
Correct |
2658 ms |
230000 KB |
Output is correct |
39 |
Correct |
941 ms |
230496 KB |
Output is correct |
40 |
Correct |
1401 ms |
118964 KB |
Output is correct |
41 |
Correct |
3532 ms |
230472 KB |
Output is correct |
42 |
Correct |
820 ms |
230012 KB |
Output is correct |
43 |
Correct |
573 ms |
2516 KB |
Output is correct |
44 |
Correct |
636 ms |
2384 KB |
Output is correct |
45 |
Correct |
531 ms |
2660 KB |
Output is correct |
46 |
Correct |
469 ms |
2444 KB |
Output is correct |
47 |
Correct |
517 ms |
2436 KB |
Output is correct |
48 |
Correct |
524 ms |
2400 KB |
Output is correct |
49 |
Correct |
534 ms |
2676 KB |
Output is correct |
50 |
Correct |
476 ms |
2384 KB |
Output is correct |
51 |
Correct |
500 ms |
3060 KB |
Output is correct |
52 |
Correct |
450 ms |
2460 KB |
Output is correct |
53 |
Correct |
510 ms |
2572 KB |
Output is correct |
54 |
Correct |
464 ms |
2644 KB |
Output is correct |
55 |
Correct |
490 ms |
2428 KB |
Output is correct |
56 |
Correct |
495 ms |
2636 KB |
Output is correct |
57 |
Correct |
497 ms |
2664 KB |
Output is correct |
58 |
Correct |
462 ms |
2388 KB |
Output is correct |
59 |
Correct |
500 ms |
2484 KB |
Output is correct |
60 |
Correct |
498 ms |
2640 KB |
Output is correct |
61 |
Correct |
496 ms |
2644 KB |
Output is correct |
62 |
Correct |
499 ms |
2584 KB |
Output is correct |
63 |
Correct |
496 ms |
2672 KB |
Output is correct |
64 |
Correct |
494 ms |
2588 KB |
Output is correct |
65 |
Correct |
505 ms |
2648 KB |
Output is correct |
66 |
Correct |
494 ms |
2676 KB |
Output is correct |
67 |
Correct |
481 ms |
2564 KB |
Output is correct |
68 |
Correct |
503 ms |
2612 KB |
Output is correct |
69 |
Correct |
2739 ms |
228676 KB |
Output is correct |
70 |
Correct |
2891 ms |
230440 KB |
Output is correct |
71 |
Correct |
816 ms |
17308 KB |
Output is correct |
72 |
Correct |
817 ms |
17580 KB |
Output is correct |
73 |
Correct |
809 ms |
17416 KB |
Output is correct |
74 |
Correct |
1400 ms |
228208 KB |
Output is correct |
75 |
Correct |
809 ms |
17352 KB |
Output is correct |
76 |
Correct |
1545 ms |
230396 KB |
Output is correct |
77 |
Correct |
1602 ms |
228856 KB |
Output is correct |
78 |
Correct |
855 ms |
17396 KB |
Output is correct |
79 |
Correct |
890 ms |
17364 KB |
Output is correct |
80 |
Correct |
1634 ms |
226940 KB |
Output is correct |
81 |
Correct |
909 ms |
17336 KB |
Output is correct |
82 |
Correct |
1615 ms |
230656 KB |
Output is correct |
83 |
Correct |
1698 ms |
229424 KB |
Output is correct |
84 |
Correct |
874 ms |
17516 KB |
Output is correct |
85 |
Correct |
851 ms |
17240 KB |
Output is correct |
86 |
Correct |
2144 ms |
227616 KB |
Output is correct |
87 |
Correct |
2105 ms |
230340 KB |
Output is correct |
88 |
Correct |
931 ms |
17376 KB |
Output is correct |
89 |
Correct |
1945 ms |
228672 KB |
Output is correct |
90 |
Correct |
1896 ms |
230436 KB |
Output is correct |
91 |
Correct |
860 ms |
17488 KB |
Output is correct |
92 |
Correct |
1389 ms |
227392 KB |
Output is correct |
93 |
Correct |
779 ms |
17376 KB |
Output is correct |
94 |
Correct |
781 ms |
17492 KB |
Output is correct |
95 |
Correct |
820 ms |
17484 KB |
Output is correct |
96 |
Correct |
2417 ms |
230264 KB |
Output is correct |
97 |
Correct |
956 ms |
230548 KB |
Output is correct |
98 |
Correct |
1466 ms |
118736 KB |
Output is correct |
99 |
Correct |
3830 ms |
230556 KB |
Output is correct |
100 |
Correct |
838 ms |
229780 KB |
Output is correct |