#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int ll
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
uniform_int_distribution<ll> uid(l, r);
return uid(rng);
}
int pr[maxn][3], seg[4*maxn], lz[4*maxn];
void push(int i, int l, int r) {
if (lz[i] == 3) return;
seg[i] = pr[r][lz[i]] ^ pr[l-1][lz[i]];
if (l != r) lz[2*i] = lz[2*i+1] = lz[i];
lz[i] = 3;
}
void upd(int i, int l, int r, int x, int y, int k) {
push(i, l, r);
if (r < x || y < l) return;
if (x <= l && r <= y) {
lz[i] = k;
push(i, l, r);
return;
}
int md = (l + r) / 2;
upd(2*i, l, md, x, y, k), upd(2*i+1, md+1, r, x, y, k);
seg[i] = seg[2*i] ^ seg[2*i+1];
}
int32_t main(){_
int n; cin >> n; string a, b, c; cin >> a >> b >> c;
// there are only 27 strings that can be generated (trust)
map<char, int> f;
f['J'] = 2, f['O'] = 0, f['I'] = 1;
for (int i = 0; i < 3; ++i) {
for (int j = 1; j <= n; ++j) {
pr[j][i] = pr[j-1][i] ^ rnd(0, 8e18);
}
}
map<int, bool> existe;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
int x = 0;
if (i + j + k == 0) continue;
if (max({i, j, k}) == 2 && i + j + k == 3) continue;
for (int w = 1; w <= n; ++w) {
int ac = f[a[w-1]], bc = f[b[w-1]], cc = f[c[w-1]];
int res = (ac * i + bc * j + cc * k) % 3;
if (ac == bc && bc == cc) res = ac;
x ^= pr[w][res] ^ pr[w-1][res];
}
existe[x] = 1;
}
}
}
for (int i = 1; i < 4*maxn; ++i) lz[i] = 3;
int q; cin >> q;
string t; cin >> t;
for (int i = 1; i <= n; ++i) upd(1, 1, n, i, i, f[t[i-1]]);
cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;
while (q--) {
int l, r; char c; cin >> l >> r >> c;
upd(1, 1, n, l, r, f[c]);
cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
19556 KB |
Output is correct |
2 |
Correct |
136 ms |
20448 KB |
Output is correct |
3 |
Correct |
98 ms |
13900 KB |
Output is correct |
4 |
Correct |
119 ms |
20380 KB |
Output is correct |
5 |
Correct |
126 ms |
20592 KB |
Output is correct |
6 |
Correct |
111 ms |
19760 KB |
Output is correct |
7 |
Correct |
112 ms |
19964 KB |
Output is correct |
8 |
Correct |
121 ms |
20776 KB |
Output is correct |
9 |
Correct |
127 ms |
20324 KB |
Output is correct |
10 |
Correct |
142 ms |
21836 KB |
Output is correct |
11 |
Correct |
123 ms |
21116 KB |
Output is correct |
12 |
Correct |
127 ms |
21808 KB |
Output is correct |
13 |
Correct |
163 ms |
21140 KB |
Output is correct |
14 |
Correct |
123 ms |
21836 KB |
Output is correct |
15 |
Correct |
118 ms |
21064 KB |
Output is correct |
16 |
Correct |
135 ms |
21944 KB |
Output is correct |
17 |
Correct |
127 ms |
21140 KB |
Output is correct |
18 |
Correct |
78 ms |
12296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
19556 KB |
Output is correct |
2 |
Correct |
136 ms |
20448 KB |
Output is correct |
3 |
Correct |
98 ms |
13900 KB |
Output is correct |
4 |
Correct |
119 ms |
20380 KB |
Output is correct |
5 |
Correct |
126 ms |
20592 KB |
Output is correct |
6 |
Correct |
111 ms |
19760 KB |
Output is correct |
7 |
Correct |
112 ms |
19964 KB |
Output is correct |
8 |
Correct |
121 ms |
20776 KB |
Output is correct |
9 |
Correct |
127 ms |
20324 KB |
Output is correct |
10 |
Correct |
142 ms |
21836 KB |
Output is correct |
11 |
Correct |
123 ms |
21116 KB |
Output is correct |
12 |
Correct |
127 ms |
21808 KB |
Output is correct |
13 |
Correct |
163 ms |
21140 KB |
Output is correct |
14 |
Correct |
123 ms |
21836 KB |
Output is correct |
15 |
Correct |
118 ms |
21064 KB |
Output is correct |
16 |
Correct |
135 ms |
21944 KB |
Output is correct |
17 |
Correct |
127 ms |
21140 KB |
Output is correct |
18 |
Correct |
78 ms |
12296 KB |
Output is correct |
19 |
Correct |
449 ms |
29608 KB |
Output is correct |
20 |
Correct |
357 ms |
30368 KB |
Output is correct |
21 |
Correct |
337 ms |
30976 KB |
Output is correct |
22 |
Correct |
325 ms |
28280 KB |
Output is correct |
23 |
Correct |
167 ms |
23292 KB |
Output is correct |
24 |
Correct |
173 ms |
22092 KB |
Output is correct |
25 |
Correct |
347 ms |
31936 KB |
Output is correct |
26 |
Correct |
340 ms |
29980 KB |
Output is correct |
27 |
Correct |
347 ms |
32312 KB |
Output is correct |
28 |
Correct |
350 ms |
29924 KB |
Output is correct |
29 |
Correct |
330 ms |
31904 KB |
Output is correct |
30 |
Correct |
195 ms |
23280 KB |
Output is correct |
31 |
Correct |
382 ms |
32300 KB |
Output is correct |
32 |
Correct |
319 ms |
29336 KB |
Output is correct |
33 |
Correct |
160 ms |
21920 KB |
Output is correct |
34 |
Correct |
344 ms |
30012 KB |
Output is correct |
35 |
Correct |
278 ms |
28796 KB |
Output is correct |
36 |
Correct |
205 ms |
22104 KB |
Output is correct |
37 |
Correct |
170 ms |
22092 KB |
Output is correct |
38 |
Correct |
276 ms |
27640 KB |
Output is correct |
39 |
Correct |
247 ms |
26292 KB |
Output is correct |
40 |
Correct |
272 ms |
26412 KB |
Output is correct |
41 |
Correct |
306 ms |
20140 KB |
Output is correct |
42 |
Correct |
128 ms |
20124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
19556 KB |
Output is correct |
2 |
Correct |
136 ms |
20448 KB |
Output is correct |
3 |
Correct |
98 ms |
13900 KB |
Output is correct |
4 |
Correct |
119 ms |
20380 KB |
Output is correct |
5 |
Correct |
126 ms |
20592 KB |
Output is correct |
6 |
Correct |
111 ms |
19760 KB |
Output is correct |
7 |
Correct |
112 ms |
19964 KB |
Output is correct |
8 |
Correct |
121 ms |
20776 KB |
Output is correct |
9 |
Correct |
127 ms |
20324 KB |
Output is correct |
10 |
Correct |
142 ms |
21836 KB |
Output is correct |
11 |
Correct |
123 ms |
21116 KB |
Output is correct |
12 |
Correct |
127 ms |
21808 KB |
Output is correct |
13 |
Correct |
163 ms |
21140 KB |
Output is correct |
14 |
Correct |
123 ms |
21836 KB |
Output is correct |
15 |
Correct |
118 ms |
21064 KB |
Output is correct |
16 |
Correct |
135 ms |
21944 KB |
Output is correct |
17 |
Correct |
127 ms |
21140 KB |
Output is correct |
18 |
Correct |
78 ms |
12296 KB |
Output is correct |
19 |
Correct |
114 ms |
19964 KB |
Output is correct |
20 |
Correct |
119 ms |
13980 KB |
Output is correct |
21 |
Correct |
121 ms |
21204 KB |
Output is correct |
22 |
Correct |
102 ms |
19276 KB |
Output is correct |
23 |
Correct |
127 ms |
21304 KB |
Output is correct |
24 |
Correct |
125 ms |
20176 KB |
Output is correct |
25 |
Correct |
146 ms |
21156 KB |
Output is correct |
26 |
Correct |
111 ms |
19916 KB |
Output is correct |
27 |
Correct |
120 ms |
21280 KB |
Output is correct |
28 |
Correct |
118 ms |
20204 KB |
Output is correct |
29 |
Correct |
126 ms |
20644 KB |
Output is correct |
30 |
Correct |
110 ms |
19584 KB |
Output is correct |
31 |
Correct |
124 ms |
21504 KB |
Output is correct |
32 |
Correct |
122 ms |
21376 KB |
Output is correct |
33 |
Correct |
123 ms |
20796 KB |
Output is correct |
34 |
Correct |
111 ms |
19940 KB |
Output is correct |
35 |
Correct |
142 ms |
21864 KB |
Output is correct |
36 |
Correct |
123 ms |
21084 KB |
Output is correct |
37 |
Correct |
123 ms |
21920 KB |
Output is correct |
38 |
Correct |
139 ms |
21132 KB |
Output is correct |
39 |
Correct |
129 ms |
21876 KB |
Output is correct |
40 |
Correct |
119 ms |
21048 KB |
Output is correct |
41 |
Correct |
125 ms |
21872 KB |
Output is correct |
42 |
Correct |
134 ms |
21140 KB |
Output is correct |
43 |
Incorrect |
128 ms |
20396 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
19556 KB |
Output is correct |
2 |
Correct |
136 ms |
20448 KB |
Output is correct |
3 |
Correct |
98 ms |
13900 KB |
Output is correct |
4 |
Correct |
119 ms |
20380 KB |
Output is correct |
5 |
Correct |
126 ms |
20592 KB |
Output is correct |
6 |
Correct |
111 ms |
19760 KB |
Output is correct |
7 |
Correct |
112 ms |
19964 KB |
Output is correct |
8 |
Correct |
121 ms |
20776 KB |
Output is correct |
9 |
Correct |
127 ms |
20324 KB |
Output is correct |
10 |
Correct |
142 ms |
21836 KB |
Output is correct |
11 |
Correct |
123 ms |
21116 KB |
Output is correct |
12 |
Correct |
127 ms |
21808 KB |
Output is correct |
13 |
Correct |
163 ms |
21140 KB |
Output is correct |
14 |
Correct |
123 ms |
21836 KB |
Output is correct |
15 |
Correct |
118 ms |
21064 KB |
Output is correct |
16 |
Correct |
135 ms |
21944 KB |
Output is correct |
17 |
Correct |
127 ms |
21140 KB |
Output is correct |
18 |
Correct |
78 ms |
12296 KB |
Output is correct |
19 |
Correct |
449 ms |
29608 KB |
Output is correct |
20 |
Correct |
357 ms |
30368 KB |
Output is correct |
21 |
Correct |
337 ms |
30976 KB |
Output is correct |
22 |
Correct |
325 ms |
28280 KB |
Output is correct |
23 |
Correct |
167 ms |
23292 KB |
Output is correct |
24 |
Correct |
173 ms |
22092 KB |
Output is correct |
25 |
Correct |
347 ms |
31936 KB |
Output is correct |
26 |
Correct |
340 ms |
29980 KB |
Output is correct |
27 |
Correct |
347 ms |
32312 KB |
Output is correct |
28 |
Correct |
350 ms |
29924 KB |
Output is correct |
29 |
Correct |
330 ms |
31904 KB |
Output is correct |
30 |
Correct |
195 ms |
23280 KB |
Output is correct |
31 |
Correct |
382 ms |
32300 KB |
Output is correct |
32 |
Correct |
319 ms |
29336 KB |
Output is correct |
33 |
Correct |
160 ms |
21920 KB |
Output is correct |
34 |
Correct |
344 ms |
30012 KB |
Output is correct |
35 |
Correct |
278 ms |
28796 KB |
Output is correct |
36 |
Correct |
205 ms |
22104 KB |
Output is correct |
37 |
Correct |
170 ms |
22092 KB |
Output is correct |
38 |
Correct |
276 ms |
27640 KB |
Output is correct |
39 |
Correct |
247 ms |
26292 KB |
Output is correct |
40 |
Correct |
272 ms |
26412 KB |
Output is correct |
41 |
Correct |
306 ms |
20140 KB |
Output is correct |
42 |
Correct |
128 ms |
20124 KB |
Output is correct |
43 |
Correct |
114 ms |
19964 KB |
Output is correct |
44 |
Correct |
119 ms |
13980 KB |
Output is correct |
45 |
Correct |
121 ms |
21204 KB |
Output is correct |
46 |
Correct |
102 ms |
19276 KB |
Output is correct |
47 |
Correct |
127 ms |
21304 KB |
Output is correct |
48 |
Correct |
125 ms |
20176 KB |
Output is correct |
49 |
Correct |
146 ms |
21156 KB |
Output is correct |
50 |
Correct |
111 ms |
19916 KB |
Output is correct |
51 |
Correct |
120 ms |
21280 KB |
Output is correct |
52 |
Correct |
118 ms |
20204 KB |
Output is correct |
53 |
Correct |
126 ms |
20644 KB |
Output is correct |
54 |
Correct |
110 ms |
19584 KB |
Output is correct |
55 |
Correct |
124 ms |
21504 KB |
Output is correct |
56 |
Correct |
122 ms |
21376 KB |
Output is correct |
57 |
Correct |
123 ms |
20796 KB |
Output is correct |
58 |
Correct |
111 ms |
19940 KB |
Output is correct |
59 |
Correct |
142 ms |
21864 KB |
Output is correct |
60 |
Correct |
123 ms |
21084 KB |
Output is correct |
61 |
Correct |
123 ms |
21920 KB |
Output is correct |
62 |
Correct |
139 ms |
21132 KB |
Output is correct |
63 |
Correct |
129 ms |
21876 KB |
Output is correct |
64 |
Correct |
119 ms |
21048 KB |
Output is correct |
65 |
Correct |
125 ms |
21872 KB |
Output is correct |
66 |
Correct |
134 ms |
21140 KB |
Output is correct |
67 |
Incorrect |
128 ms |
20396 KB |
Output isn't correct |
68 |
Halted |
0 ms |
0 KB |
- |