#include <bits/stdc++.h>
using namespace std;
struct Cell {
char sym;
bool same;
Cell() { sym = -2, same = true; }
Cell operator+(const Cell& other) const {
if (sym == -2) {
return other;
}
if (other.sym == -2) {
return *this;
}
Cell res;
if (sym == -1 || other.sym == -1 || sym != other.sym) {
res.sym = -1;
} else {
res.sym = sym;
}
res.same = same && other.same;
return res;
}
~Cell() {}
};
struct SegTree {
int n, N;
vector<char> lazy;
vector<Cell> st;
SegTree() {}
SegTree(int _n, const string& s) {
n = _n, N = 1;
while (N < n) {
N <<= 1;
}
st.resize(2 * N);
lazy.resize(2 * N, -1);
for (int i = 0; i < n; ++i) {
st[N + i].sym = s[i];
// cerr << "v: " << N + i << ", sym: " << st[N + i].sym << '\n';
}
for (int i = N - 1; i > 0; --i) {
st[i] = st[2 * i] + st[2 * i + 1];
// cerr << "v: " << i << ", sym: " << st[i].sym << '\n';
}
}
void push(int v) {
// cerr << "v: " << v << ", lazy: " << lazy[v] << ' ';
if (st[v].sym == lazy[v]) {
st[v].same = true;
} else {
st[v].same = false;
}
// cerr << "same: " << st[v].same << '\n';
if (v < N) {
lazy[2 * v] = lazy[v];
lazy[2 * v + 1] = lazy[v];
}
lazy[v] = -1;
}
void assign(int v, int tl, int tr, int l, int r, char c) {
if (lazy[v] != -1) {
push(v);
}
if (tl >= r || tr <= l) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] = c;
push(v);
return;
}
int m = tl + (tr - tl) / 2;
assign(2 * v, tl, m, l, r, c);
assign(2 * v + 1, m, tr, l, r, c);
st[v] = st[2 * v] + st[2 * v + 1];
// cerr << "v: " << v << ", same: " << st[v].same << '\n';
}
void assign(int l, int r, char c) {
assign(1, 0, N, l, r, c);
}
bool query() {
if (lazy[1] != -1) {
push(1);
}
return st[1].same;
}
~SegTree() {}
};
void solve() {
int n;
cin >> n;
string s;
cin >> s >> s >> s;
int q;
cin >> q;
string t;
cin >> t;
SegTree st(n, s);
for (int i = 0; i < n; ++i) {
st.assign(i, i + 1, t[i]);
}
if (st.query()) {
cout << "Yes\n";
} else {
cout << "No\n";
}
while (q--) {
int l, r;
char c;
cin >> l >> r >> c;
--l;
st.assign(l, r, c);
if (st.query()) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
2392 KB |
Output is correct |
2 |
Correct |
57 ms |
2388 KB |
Output is correct |
3 |
Correct |
54 ms |
2384 KB |
Output is correct |
4 |
Correct |
50 ms |
2388 KB |
Output is correct |
5 |
Correct |
48 ms |
2456 KB |
Output is correct |
6 |
Correct |
63 ms |
2356 KB |
Output is correct |
7 |
Correct |
50 ms |
2384 KB |
Output is correct |
8 |
Correct |
53 ms |
2580 KB |
Output is correct |
9 |
Correct |
56 ms |
2536 KB |
Output is correct |
10 |
Correct |
50 ms |
2524 KB |
Output is correct |
11 |
Correct |
51 ms |
2388 KB |
Output is correct |
12 |
Correct |
50 ms |
2384 KB |
Output is correct |
13 |
Correct |
54 ms |
2568 KB |
Output is correct |
14 |
Correct |
50 ms |
2392 KB |
Output is correct |
15 |
Correct |
51 ms |
2432 KB |
Output is correct |
16 |
Correct |
51 ms |
2380 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
61 ms |
2564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
2392 KB |
Output is correct |
2 |
Correct |
57 ms |
2388 KB |
Output is correct |
3 |
Correct |
54 ms |
2384 KB |
Output is correct |
4 |
Correct |
50 ms |
2388 KB |
Output is correct |
5 |
Correct |
48 ms |
2456 KB |
Output is correct |
6 |
Correct |
63 ms |
2356 KB |
Output is correct |
7 |
Correct |
50 ms |
2384 KB |
Output is correct |
8 |
Correct |
53 ms |
2580 KB |
Output is correct |
9 |
Correct |
56 ms |
2536 KB |
Output is correct |
10 |
Correct |
50 ms |
2524 KB |
Output is correct |
11 |
Correct |
51 ms |
2388 KB |
Output is correct |
12 |
Correct |
50 ms |
2384 KB |
Output is correct |
13 |
Correct |
54 ms |
2568 KB |
Output is correct |
14 |
Correct |
50 ms |
2392 KB |
Output is correct |
15 |
Correct |
51 ms |
2432 KB |
Output is correct |
16 |
Correct |
51 ms |
2380 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
61 ms |
2564 KB |
Output is correct |
19 |
Correct |
170 ms |
6792 KB |
Output is correct |
20 |
Correct |
191 ms |
6536 KB |
Output is correct |
21 |
Correct |
154 ms |
6508 KB |
Output is correct |
22 |
Correct |
128 ms |
6140 KB |
Output is correct |
23 |
Correct |
80 ms |
3408 KB |
Output is correct |
24 |
Correct |
79 ms |
3488 KB |
Output is correct |
25 |
Correct |
137 ms |
6788 KB |
Output is correct |
26 |
Correct |
137 ms |
6792 KB |
Output is correct |
27 |
Correct |
154 ms |
6592 KB |
Output is correct |
28 |
Correct |
164 ms |
6672 KB |
Output is correct |
29 |
Correct |
173 ms |
6524 KB |
Output is correct |
30 |
Correct |
90 ms |
3444 KB |
Output is correct |
31 |
Correct |
160 ms |
6668 KB |
Output is correct |
32 |
Correct |
174 ms |
6384 KB |
Output is correct |
33 |
Correct |
80 ms |
3416 KB |
Output is correct |
34 |
Correct |
154 ms |
6608 KB |
Output is correct |
35 |
Correct |
116 ms |
6056 KB |
Output is correct |
36 |
Correct |
89 ms |
3484 KB |
Output is correct |
37 |
Correct |
80 ms |
3332 KB |
Output is correct |
38 |
Correct |
164 ms |
6536 KB |
Output is correct |
39 |
Correct |
126 ms |
6784 KB |
Output is correct |
40 |
Correct |
113 ms |
5388 KB |
Output is correct |
41 |
Correct |
188 ms |
7000 KB |
Output is correct |
42 |
Correct |
95 ms |
6076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
2392 KB |
Output is correct |
2 |
Correct |
57 ms |
2388 KB |
Output is correct |
3 |
Correct |
54 ms |
2384 KB |
Output is correct |
4 |
Correct |
50 ms |
2388 KB |
Output is correct |
5 |
Correct |
48 ms |
2456 KB |
Output is correct |
6 |
Correct |
63 ms |
2356 KB |
Output is correct |
7 |
Correct |
50 ms |
2384 KB |
Output is correct |
8 |
Correct |
53 ms |
2580 KB |
Output is correct |
9 |
Correct |
56 ms |
2536 KB |
Output is correct |
10 |
Correct |
50 ms |
2524 KB |
Output is correct |
11 |
Correct |
51 ms |
2388 KB |
Output is correct |
12 |
Correct |
50 ms |
2384 KB |
Output is correct |
13 |
Correct |
54 ms |
2568 KB |
Output is correct |
14 |
Correct |
50 ms |
2392 KB |
Output is correct |
15 |
Correct |
51 ms |
2432 KB |
Output is correct |
16 |
Correct |
51 ms |
2380 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
61 ms |
2564 KB |
Output is correct |
19 |
Correct |
54 ms |
2440 KB |
Output is correct |
20 |
Correct |
64 ms |
2388 KB |
Output is correct |
21 |
Incorrect |
50 ms |
2452 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
2392 KB |
Output is correct |
2 |
Correct |
57 ms |
2388 KB |
Output is correct |
3 |
Correct |
54 ms |
2384 KB |
Output is correct |
4 |
Correct |
50 ms |
2388 KB |
Output is correct |
5 |
Correct |
48 ms |
2456 KB |
Output is correct |
6 |
Correct |
63 ms |
2356 KB |
Output is correct |
7 |
Correct |
50 ms |
2384 KB |
Output is correct |
8 |
Correct |
53 ms |
2580 KB |
Output is correct |
9 |
Correct |
56 ms |
2536 KB |
Output is correct |
10 |
Correct |
50 ms |
2524 KB |
Output is correct |
11 |
Correct |
51 ms |
2388 KB |
Output is correct |
12 |
Correct |
50 ms |
2384 KB |
Output is correct |
13 |
Correct |
54 ms |
2568 KB |
Output is correct |
14 |
Correct |
50 ms |
2392 KB |
Output is correct |
15 |
Correct |
51 ms |
2432 KB |
Output is correct |
16 |
Correct |
51 ms |
2380 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
61 ms |
2564 KB |
Output is correct |
19 |
Correct |
170 ms |
6792 KB |
Output is correct |
20 |
Correct |
191 ms |
6536 KB |
Output is correct |
21 |
Correct |
154 ms |
6508 KB |
Output is correct |
22 |
Correct |
128 ms |
6140 KB |
Output is correct |
23 |
Correct |
80 ms |
3408 KB |
Output is correct |
24 |
Correct |
79 ms |
3488 KB |
Output is correct |
25 |
Correct |
137 ms |
6788 KB |
Output is correct |
26 |
Correct |
137 ms |
6792 KB |
Output is correct |
27 |
Correct |
154 ms |
6592 KB |
Output is correct |
28 |
Correct |
164 ms |
6672 KB |
Output is correct |
29 |
Correct |
173 ms |
6524 KB |
Output is correct |
30 |
Correct |
90 ms |
3444 KB |
Output is correct |
31 |
Correct |
160 ms |
6668 KB |
Output is correct |
32 |
Correct |
174 ms |
6384 KB |
Output is correct |
33 |
Correct |
80 ms |
3416 KB |
Output is correct |
34 |
Correct |
154 ms |
6608 KB |
Output is correct |
35 |
Correct |
116 ms |
6056 KB |
Output is correct |
36 |
Correct |
89 ms |
3484 KB |
Output is correct |
37 |
Correct |
80 ms |
3332 KB |
Output is correct |
38 |
Correct |
164 ms |
6536 KB |
Output is correct |
39 |
Correct |
126 ms |
6784 KB |
Output is correct |
40 |
Correct |
113 ms |
5388 KB |
Output is correct |
41 |
Correct |
188 ms |
7000 KB |
Output is correct |
42 |
Correct |
95 ms |
6076 KB |
Output is correct |
43 |
Correct |
54 ms |
2440 KB |
Output is correct |
44 |
Correct |
64 ms |
2388 KB |
Output is correct |
45 |
Incorrect |
50 ms |
2452 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |