#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct Node {
int cnt_s[3], cnt_t[3], lazy;
bool match;
Node() {
cnt_s[0] = cnt_s[1] = cnt_s[2] = 0;
cnt_t[0] = cnt_t[1] = cnt_t[2] = 0;
lazy = -1;
}
};
int n, q;
string s, t;
vector<Node> sgt;
int id(char c) {
if (c == 'J') return 0;
else if (c == 'O') return 1;
else return 2;
}
void init(int u, int l, int r) {
if (l == r) {
sgt[u].cnt_s[id(s[l])]++;
sgt[u].cnt_t[id(t[l])]++;
sgt[u].match = (s[l] == t[l]);
} else {
int mid = (l + r) / 2;
init(2 * u, l, mid);
init(2 * u + 1, mid + 1, r);
for (int i = 0; i < 3; i++) {
sgt[u].cnt_s[i] = sgt[2 * u].cnt_s[i] + sgt[2 * u + 1].cnt_s[i];
sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
}
sgt[u].match = (sgt[2 * u].match & sgt[2 * u + 1].match);
}
}
void update(int u, int l, int r, int L, int R, int x) {
if (r < L or R < l) return;
else if (L <= l and r <= R) {
memset(sgt[u].cnt_t, 0, sizeof(sgt[u].cnt_t));
sgt[u].cnt_t[x] = r - l + 1;
sgt[u].lazy = x;
sgt[u].match = (sgt[u].cnt_s[x] == sgt[u].cnt_t[x]);
} else {
int mid = (l + r) / 2;
if (sgt[u].lazy != -1) {
memset(sgt[2 * u].cnt_t, 0, sizeof(sgt[2 * u].cnt_t));
memset(sgt[2 * u + 1].cnt_t, 0, sizeof(sgt[2 * u + 1].cnt_t));
sgt[2 * u].cnt_t[sgt[u].lazy] = mid - l + 1;
sgt[2 * u].match = (sgt[2 * u].cnt_s[sgt[u].lazy] == sgt[2 * u].cnt_t[sgt[u].lazy]);
sgt[2 * u + 1].cnt_t[sgt[u].lazy] = r - mid;
sgt[2 * u + 1].match = (sgt[2 * u + 1].cnt_s[sgt[u].lazy] == sgt[2 * u + 1].cnt_t[sgt[u].lazy]);
sgt[2 * u].lazy = sgt[2 * u + 1].lazy = sgt[u].lazy;
sgt[u].lazy = -1;
}
update(2 * u, l, mid, L, R, x);
update(2 * u + 1, mid + 1, r, L, R, x);
for (int i = 0; i < 3; i++) {
sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
}
sgt[u].match = (sgt[2 * u].match & sgt[2 * u + 1].match);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s >> s >> s >> q >> t;
sgt.resize(4 * n, Node());
init(1, 0, n - 1);
cout << (sgt[1].match ? "Yes" : "No") << endl;
while (q--) {
int l, r;
char c;
cin >> l >> r >> c;
update(1, 0, n - 1, l - 1, r - 1, id(c));
cout << (sgt[1].match ? "Yes" : "No") << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
2252 KB |
Output is correct |
2 |
Correct |
311 ms |
2428 KB |
Output is correct |
3 |
Correct |
301 ms |
2268 KB |
Output is correct |
4 |
Correct |
285 ms |
2284 KB |
Output is correct |
5 |
Correct |
275 ms |
2264 KB |
Output is correct |
6 |
Correct |
277 ms |
2220 KB |
Output is correct |
7 |
Correct |
277 ms |
2376 KB |
Output is correct |
8 |
Correct |
290 ms |
2532 KB |
Output is correct |
9 |
Correct |
294 ms |
2468 KB |
Output is correct |
10 |
Correct |
299 ms |
2448 KB |
Output is correct |
11 |
Correct |
311 ms |
2320 KB |
Output is correct |
12 |
Correct |
299 ms |
2380 KB |
Output is correct |
13 |
Correct |
292 ms |
2548 KB |
Output is correct |
14 |
Correct |
291 ms |
2444 KB |
Output is correct |
15 |
Correct |
298 ms |
2708 KB |
Output is correct |
16 |
Correct |
286 ms |
2388 KB |
Output is correct |
17 |
Correct |
290 ms |
2472 KB |
Output is correct |
18 |
Correct |
308 ms |
2264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
2252 KB |
Output is correct |
2 |
Correct |
311 ms |
2428 KB |
Output is correct |
3 |
Correct |
301 ms |
2268 KB |
Output is correct |
4 |
Correct |
285 ms |
2284 KB |
Output is correct |
5 |
Correct |
275 ms |
2264 KB |
Output is correct |
6 |
Correct |
277 ms |
2220 KB |
Output is correct |
7 |
Correct |
277 ms |
2376 KB |
Output is correct |
8 |
Correct |
290 ms |
2532 KB |
Output is correct |
9 |
Correct |
294 ms |
2468 KB |
Output is correct |
10 |
Correct |
299 ms |
2448 KB |
Output is correct |
11 |
Correct |
311 ms |
2320 KB |
Output is correct |
12 |
Correct |
299 ms |
2380 KB |
Output is correct |
13 |
Correct |
292 ms |
2548 KB |
Output is correct |
14 |
Correct |
291 ms |
2444 KB |
Output is correct |
15 |
Correct |
298 ms |
2708 KB |
Output is correct |
16 |
Correct |
286 ms |
2388 KB |
Output is correct |
17 |
Correct |
290 ms |
2472 KB |
Output is correct |
18 |
Correct |
308 ms |
2264 KB |
Output is correct |
19 |
Correct |
472 ms |
30336 KB |
Output is correct |
20 |
Correct |
407 ms |
30012 KB |
Output is correct |
21 |
Correct |
390 ms |
28328 KB |
Output is correct |
22 |
Correct |
368 ms |
25756 KB |
Output is correct |
23 |
Correct |
356 ms |
4480 KB |
Output is correct |
24 |
Correct |
319 ms |
4552 KB |
Output is correct |
25 |
Correct |
417 ms |
30164 KB |
Output is correct |
26 |
Correct |
383 ms |
30080 KB |
Output is correct |
27 |
Correct |
436 ms |
30136 KB |
Output is correct |
28 |
Correct |
438 ms |
30208 KB |
Output is correct |
29 |
Correct |
379 ms |
29304 KB |
Output is correct |
30 |
Correct |
354 ms |
4548 KB |
Output is correct |
31 |
Correct |
410 ms |
30096 KB |
Output is correct |
32 |
Correct |
384 ms |
27732 KB |
Output is correct |
33 |
Correct |
311 ms |
4448 KB |
Output is correct |
34 |
Correct |
413 ms |
30060 KB |
Output is correct |
35 |
Correct |
369 ms |
23084 KB |
Output is correct |
36 |
Correct |
336 ms |
4520 KB |
Output is correct |
37 |
Correct |
316 ms |
4436 KB |
Output is correct |
38 |
Correct |
423 ms |
29892 KB |
Output is correct |
39 |
Correct |
367 ms |
30192 KB |
Output is correct |
40 |
Correct |
389 ms |
21028 KB |
Output is correct |
41 |
Correct |
543 ms |
30476 KB |
Output is correct |
42 |
Correct |
278 ms |
29516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
2252 KB |
Output is correct |
2 |
Correct |
311 ms |
2428 KB |
Output is correct |
3 |
Correct |
301 ms |
2268 KB |
Output is correct |
4 |
Correct |
285 ms |
2284 KB |
Output is correct |
5 |
Correct |
275 ms |
2264 KB |
Output is correct |
6 |
Correct |
277 ms |
2220 KB |
Output is correct |
7 |
Correct |
277 ms |
2376 KB |
Output is correct |
8 |
Correct |
290 ms |
2532 KB |
Output is correct |
9 |
Correct |
294 ms |
2468 KB |
Output is correct |
10 |
Correct |
299 ms |
2448 KB |
Output is correct |
11 |
Correct |
311 ms |
2320 KB |
Output is correct |
12 |
Correct |
299 ms |
2380 KB |
Output is correct |
13 |
Correct |
292 ms |
2548 KB |
Output is correct |
14 |
Correct |
291 ms |
2444 KB |
Output is correct |
15 |
Correct |
298 ms |
2708 KB |
Output is correct |
16 |
Correct |
286 ms |
2388 KB |
Output is correct |
17 |
Correct |
290 ms |
2472 KB |
Output is correct |
18 |
Correct |
308 ms |
2264 KB |
Output is correct |
19 |
Correct |
284 ms |
2348 KB |
Output is correct |
20 |
Correct |
291 ms |
2240 KB |
Output is correct |
21 |
Incorrect |
286 ms |
2408 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
2252 KB |
Output is correct |
2 |
Correct |
311 ms |
2428 KB |
Output is correct |
3 |
Correct |
301 ms |
2268 KB |
Output is correct |
4 |
Correct |
285 ms |
2284 KB |
Output is correct |
5 |
Correct |
275 ms |
2264 KB |
Output is correct |
6 |
Correct |
277 ms |
2220 KB |
Output is correct |
7 |
Correct |
277 ms |
2376 KB |
Output is correct |
8 |
Correct |
290 ms |
2532 KB |
Output is correct |
9 |
Correct |
294 ms |
2468 KB |
Output is correct |
10 |
Correct |
299 ms |
2448 KB |
Output is correct |
11 |
Correct |
311 ms |
2320 KB |
Output is correct |
12 |
Correct |
299 ms |
2380 KB |
Output is correct |
13 |
Correct |
292 ms |
2548 KB |
Output is correct |
14 |
Correct |
291 ms |
2444 KB |
Output is correct |
15 |
Correct |
298 ms |
2708 KB |
Output is correct |
16 |
Correct |
286 ms |
2388 KB |
Output is correct |
17 |
Correct |
290 ms |
2472 KB |
Output is correct |
18 |
Correct |
308 ms |
2264 KB |
Output is correct |
19 |
Correct |
472 ms |
30336 KB |
Output is correct |
20 |
Correct |
407 ms |
30012 KB |
Output is correct |
21 |
Correct |
390 ms |
28328 KB |
Output is correct |
22 |
Correct |
368 ms |
25756 KB |
Output is correct |
23 |
Correct |
356 ms |
4480 KB |
Output is correct |
24 |
Correct |
319 ms |
4552 KB |
Output is correct |
25 |
Correct |
417 ms |
30164 KB |
Output is correct |
26 |
Correct |
383 ms |
30080 KB |
Output is correct |
27 |
Correct |
436 ms |
30136 KB |
Output is correct |
28 |
Correct |
438 ms |
30208 KB |
Output is correct |
29 |
Correct |
379 ms |
29304 KB |
Output is correct |
30 |
Correct |
354 ms |
4548 KB |
Output is correct |
31 |
Correct |
410 ms |
30096 KB |
Output is correct |
32 |
Correct |
384 ms |
27732 KB |
Output is correct |
33 |
Correct |
311 ms |
4448 KB |
Output is correct |
34 |
Correct |
413 ms |
30060 KB |
Output is correct |
35 |
Correct |
369 ms |
23084 KB |
Output is correct |
36 |
Correct |
336 ms |
4520 KB |
Output is correct |
37 |
Correct |
316 ms |
4436 KB |
Output is correct |
38 |
Correct |
423 ms |
29892 KB |
Output is correct |
39 |
Correct |
367 ms |
30192 KB |
Output is correct |
40 |
Correct |
389 ms |
21028 KB |
Output is correct |
41 |
Correct |
543 ms |
30476 KB |
Output is correct |
42 |
Correct |
278 ms |
29516 KB |
Output is correct |
43 |
Correct |
284 ms |
2348 KB |
Output is correct |
44 |
Correct |
291 ms |
2240 KB |
Output is correct |
45 |
Incorrect |
286 ms |
2408 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |