#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
// second mod 998244353
const ll N = 3e5 + 5;
ll n; string s, t;
struct nd {
ll o = 0, j = 0, i = 0;
ll sm = 0;
} seg[3000006];
char lazy[3000006];
inline void upd(ll node, bool b) {
if (lazy[node] == 'f') return;
seg[node].sm = 0;
char c = lazy[node];
if (c == 'O') seg[node].sm = seg[node].o;
if (c == 'J') seg[node].sm = seg[node].j;
if (c == 'I') seg[node].sm = seg[node].i;
if (b) {
lazy[node * 2] = c;
lazy[node * 2 + 1] = c;
}
lazy[node] = 'f';
}
inline void build(ll node, ll l, ll r) {
lazy[node] = 'f';
if (l == r) {
if (s[l] == t[l]) seg[node].sm = 1;
if (s[l] == 'O') ++seg[node].o;
else if (s[l] == 'I') seg[node].i++;
else seg[node].j++;
return;
}
ll mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
seg[node].j = seg[node * 2].j + seg[node * 2 + 1].j;
seg[node].o = seg[node * 2].o + seg[node * 2 + 1].o;
seg[node].i = seg[node * 2].i + seg[node * 2 + 1].i;
seg[node].sm = seg[node * 2].sm + seg[node * 2 + 1].sm;
}
inline void update(ll node, ll l, ll r, ll lx, ll rx, char c) {
upd(node, (l != r));
if (l >= lx && r <= rx) {
lazy[node] = c;
upd(node, (l != r));
return;
}
else if (l > rx || r < lx) return;
ll mid = (l + r) / 2;
update(node * 2, l, mid, lx, rx, c);
update(node * 2 + 1, mid + 1, r, lx, rx, c);
seg[node].sm = seg[node * 2].sm + seg[node * 2 + 1].sm;
}
inline bool get() { return seg[1].sm == n; }
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
string d;
s = " "; t = " ";
cin >> n >> d >> d >> d;
s += d;
ll q; cin >> q;
cin >> d;
t += d;
build(1, 1, n);
if (get()) cout << "Yes\n";
else cout << "No\n";
for (; q--;) {
ll l, r; cin >> l >> r;
char ch; cin >> ch;
update(1, 1, n, l, r, ch);
if (get()) cout << "Yes\n";
else cout << "No\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
4336 KB |
Output is correct |
2 |
Correct |
60 ms |
4448 KB |
Output is correct |
3 |
Correct |
52 ms |
4432 KB |
Output is correct |
4 |
Correct |
53 ms |
4312 KB |
Output is correct |
5 |
Correct |
58 ms |
4336 KB |
Output is correct |
6 |
Correct |
48 ms |
4428 KB |
Output is correct |
7 |
Correct |
51 ms |
4472 KB |
Output is correct |
8 |
Correct |
50 ms |
4576 KB |
Output is correct |
9 |
Correct |
53 ms |
4576 KB |
Output is correct |
10 |
Correct |
56 ms |
4600 KB |
Output is correct |
11 |
Correct |
51 ms |
4432 KB |
Output is correct |
12 |
Correct |
50 ms |
4436 KB |
Output is correct |
13 |
Correct |
55 ms |
4444 KB |
Output is correct |
14 |
Correct |
52 ms |
4624 KB |
Output is correct |
15 |
Correct |
53 ms |
4432 KB |
Output is correct |
16 |
Correct |
53 ms |
4596 KB |
Output is correct |
17 |
Correct |
51 ms |
4432 KB |
Output is correct |
18 |
Correct |
50 ms |
4412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
4336 KB |
Output is correct |
2 |
Correct |
60 ms |
4448 KB |
Output is correct |
3 |
Correct |
52 ms |
4432 KB |
Output is correct |
4 |
Correct |
53 ms |
4312 KB |
Output is correct |
5 |
Correct |
58 ms |
4336 KB |
Output is correct |
6 |
Correct |
48 ms |
4428 KB |
Output is correct |
7 |
Correct |
51 ms |
4472 KB |
Output is correct |
8 |
Correct |
50 ms |
4576 KB |
Output is correct |
9 |
Correct |
53 ms |
4576 KB |
Output is correct |
10 |
Correct |
56 ms |
4600 KB |
Output is correct |
11 |
Correct |
51 ms |
4432 KB |
Output is correct |
12 |
Correct |
50 ms |
4436 KB |
Output is correct |
13 |
Correct |
55 ms |
4444 KB |
Output is correct |
14 |
Correct |
52 ms |
4624 KB |
Output is correct |
15 |
Correct |
53 ms |
4432 KB |
Output is correct |
16 |
Correct |
53 ms |
4596 KB |
Output is correct |
17 |
Correct |
51 ms |
4432 KB |
Output is correct |
18 |
Correct |
50 ms |
4412 KB |
Output is correct |
19 |
Correct |
190 ms |
24572 KB |
Output is correct |
20 |
Correct |
152 ms |
24540 KB |
Output is correct |
21 |
Correct |
110 ms |
24508 KB |
Output is correct |
22 |
Correct |
101 ms |
24284 KB |
Output is correct |
23 |
Correct |
74 ms |
5324 KB |
Output is correct |
24 |
Correct |
82 ms |
5452 KB |
Output is correct |
25 |
Correct |
125 ms |
24080 KB |
Output is correct |
26 |
Correct |
120 ms |
23888 KB |
Output is correct |
27 |
Correct |
117 ms |
24016 KB |
Output is correct |
28 |
Correct |
149 ms |
24048 KB |
Output is correct |
29 |
Correct |
113 ms |
23772 KB |
Output is correct |
30 |
Correct |
87 ms |
5488 KB |
Output is correct |
31 |
Correct |
114 ms |
24584 KB |
Output is correct |
32 |
Correct |
116 ms |
24540 KB |
Output is correct |
33 |
Correct |
78 ms |
5456 KB |
Output is correct |
34 |
Correct |
122 ms |
24028 KB |
Output is correct |
35 |
Correct |
109 ms |
23380 KB |
Output is correct |
36 |
Correct |
76 ms |
5516 KB |
Output is correct |
37 |
Correct |
74 ms |
5420 KB |
Output is correct |
38 |
Correct |
126 ms |
24452 KB |
Output is correct |
39 |
Correct |
87 ms |
24796 KB |
Output is correct |
40 |
Correct |
116 ms |
17120 KB |
Output is correct |
41 |
Correct |
179 ms |
25004 KB |
Output is correct |
42 |
Correct |
43 ms |
23544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
4336 KB |
Output is correct |
2 |
Correct |
60 ms |
4448 KB |
Output is correct |
3 |
Correct |
52 ms |
4432 KB |
Output is correct |
4 |
Correct |
53 ms |
4312 KB |
Output is correct |
5 |
Correct |
58 ms |
4336 KB |
Output is correct |
6 |
Correct |
48 ms |
4428 KB |
Output is correct |
7 |
Correct |
51 ms |
4472 KB |
Output is correct |
8 |
Correct |
50 ms |
4576 KB |
Output is correct |
9 |
Correct |
53 ms |
4576 KB |
Output is correct |
10 |
Correct |
56 ms |
4600 KB |
Output is correct |
11 |
Correct |
51 ms |
4432 KB |
Output is correct |
12 |
Correct |
50 ms |
4436 KB |
Output is correct |
13 |
Correct |
55 ms |
4444 KB |
Output is correct |
14 |
Correct |
52 ms |
4624 KB |
Output is correct |
15 |
Correct |
53 ms |
4432 KB |
Output is correct |
16 |
Correct |
53 ms |
4596 KB |
Output is correct |
17 |
Correct |
51 ms |
4432 KB |
Output is correct |
18 |
Correct |
50 ms |
4412 KB |
Output is correct |
19 |
Correct |
54 ms |
4384 KB |
Output is correct |
20 |
Correct |
53 ms |
4424 KB |
Output is correct |
21 |
Incorrect |
55 ms |
4440 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
4336 KB |
Output is correct |
2 |
Correct |
60 ms |
4448 KB |
Output is correct |
3 |
Correct |
52 ms |
4432 KB |
Output is correct |
4 |
Correct |
53 ms |
4312 KB |
Output is correct |
5 |
Correct |
58 ms |
4336 KB |
Output is correct |
6 |
Correct |
48 ms |
4428 KB |
Output is correct |
7 |
Correct |
51 ms |
4472 KB |
Output is correct |
8 |
Correct |
50 ms |
4576 KB |
Output is correct |
9 |
Correct |
53 ms |
4576 KB |
Output is correct |
10 |
Correct |
56 ms |
4600 KB |
Output is correct |
11 |
Correct |
51 ms |
4432 KB |
Output is correct |
12 |
Correct |
50 ms |
4436 KB |
Output is correct |
13 |
Correct |
55 ms |
4444 KB |
Output is correct |
14 |
Correct |
52 ms |
4624 KB |
Output is correct |
15 |
Correct |
53 ms |
4432 KB |
Output is correct |
16 |
Correct |
53 ms |
4596 KB |
Output is correct |
17 |
Correct |
51 ms |
4432 KB |
Output is correct |
18 |
Correct |
50 ms |
4412 KB |
Output is correct |
19 |
Correct |
190 ms |
24572 KB |
Output is correct |
20 |
Correct |
152 ms |
24540 KB |
Output is correct |
21 |
Correct |
110 ms |
24508 KB |
Output is correct |
22 |
Correct |
101 ms |
24284 KB |
Output is correct |
23 |
Correct |
74 ms |
5324 KB |
Output is correct |
24 |
Correct |
82 ms |
5452 KB |
Output is correct |
25 |
Correct |
125 ms |
24080 KB |
Output is correct |
26 |
Correct |
120 ms |
23888 KB |
Output is correct |
27 |
Correct |
117 ms |
24016 KB |
Output is correct |
28 |
Correct |
149 ms |
24048 KB |
Output is correct |
29 |
Correct |
113 ms |
23772 KB |
Output is correct |
30 |
Correct |
87 ms |
5488 KB |
Output is correct |
31 |
Correct |
114 ms |
24584 KB |
Output is correct |
32 |
Correct |
116 ms |
24540 KB |
Output is correct |
33 |
Correct |
78 ms |
5456 KB |
Output is correct |
34 |
Correct |
122 ms |
24028 KB |
Output is correct |
35 |
Correct |
109 ms |
23380 KB |
Output is correct |
36 |
Correct |
76 ms |
5516 KB |
Output is correct |
37 |
Correct |
74 ms |
5420 KB |
Output is correct |
38 |
Correct |
126 ms |
24452 KB |
Output is correct |
39 |
Correct |
87 ms |
24796 KB |
Output is correct |
40 |
Correct |
116 ms |
17120 KB |
Output is correct |
41 |
Correct |
179 ms |
25004 KB |
Output is correct |
42 |
Correct |
43 ms |
23544 KB |
Output is correct |
43 |
Correct |
54 ms |
4384 KB |
Output is correct |
44 |
Correct |
53 ms |
4424 KB |
Output is correct |
45 |
Incorrect |
55 ms |
4440 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |