#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
int n;
string t;
struct SegmentTree {
string s;
vector<int> sgt, lz;
vector<char> let, slet;
void build(int k = 1, int l = 0, int r = n - 1) {
if (l == r) {
let[k] = t[l];
if (t[l] == s[l]) sgt[k] = 1;
else sgt[k] = 0;
slet[k] = s[l];
return;
}
int m = (l + r) / 2;
build(k * 2, l, m);
build(k * 2 + 1, m + 1, r);
sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
let[k] = 'z';
if (let[k * 2] == let[k * 2 + 1]) let[k] = let[k * 2];
slet[k] = 'y';
if (slet[k * 2] == slet[k * 2 + 1]) slet[k] = slet[k * 2];
}
void init(string a) {
s = a;
sgt.resize(4 * n);
let.resize(4 * n);
slet.resize(4 * n);
lz.resize(4 * n);
build();
}
void push(int k, int l, int r) {
if (l == r) return;
if (lz[k]) {
if (l != r) lz[k * 2] = lz[k * 2 + 1] = 1;
let[k * 2] = let[k * 2 + 1] = let[k];
}
if (slet[k * 2] == let[k * 2]) sgt[k * 2] = 1;
else sgt[k * 2] = 0;
if (slet[k * 2 + 1] == let[k * 2 + 1]) sgt[k * 2 + 1] = 1;
else sgt[k * 2 + 1] = 0;
sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
lz[k] = 0;
}
void update(int k, int l, int r, int i, int j, char v) {
push(k, l, r);
if (l > j || r < i) return;
if (i <= l && r <= j) {
if (slet[k] == v) sgt[k] = 1;
else sgt[k] = 0;
let[k] = v;
lz[k] = 1;
// cout << s << " " << l << " - " << r << " " << sgt[k] << " " << let[k] << endl;
return;
}
int m = (l + r) / 2;
update(k * 2, l, m, i, j, v);
update(k * 2 + 1, m + 1, r, i, j, v);
sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
let[k] = 'z';
if (let[k * 2] == let[k * 2 + 1]) let[k] = let[k * 2];
// cout << s << " " << l << " - " << r << " " << sgt[k] << " " << let[k] << endl;
}
};
string merge(string a, string b) {
string c = "";
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[i]) c += a[i];
else {
set<char> f;
f.insert(a[i]);
f.insert(b[i]);
if (!f.count('J')) c += "J";
if (!f.count('O')) c += "O";
if (!f.count('I')) c += "I";
}
}
return c;
}
vector<SegmentTree> v(9);
int cnt;
bool pos() {
int flag = 0;
for (int i = 0; i < cnt; i++) flag = max(flag, v[i].sgt[1]);
return flag;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
string s[3];
for (int i = 0; i < 3; i++) cin >> s[i];
set<string> all;
all.insert(s[0]);
all.insert(s[1]);
all.insert(s[2]);
all.insert(merge(s[0], s[1]));
all.insert(merge(s[0], s[2]));
all.insert(merge(s[1], s[2]));
all.insert(merge(s[0], merge(s[1], s[2])));
all.insert(merge(s[1], merge(s[0], s[2])));
all.insert(merge(s[2], merge(s[0], s[1])));
int q;
cin >> q;
cin >> t;
for (auto x : all) {
v[cnt++].init(x);
}
cout << (pos() ? "Yes" : "No") << endl;
while (q--) {
int l, r;
char x;
cin >> l >> r >> x;
l--;
r--;
for (int i = 0; i < cnt; i++) v[i].update(1, 0, n - 1, l, r, x);
cout << (pos() ? "Yes" : "No") << endl;
}
}
Compilation message
Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
852 KB |
Output is correct |
| 2 |
Correct |
73 ms |
928 KB |
Output is correct |
| 3 |
Correct |
68 ms |
848 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
852 KB |
Output is correct |
| 2 |
Correct |
73 ms |
928 KB |
Output is correct |
| 3 |
Correct |
68 ms |
848 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
852 KB |
Output is correct |
| 2 |
Correct |
73 ms |
928 KB |
Output is correct |
| 3 |
Correct |
68 ms |
848 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
852 KB |
Output is correct |
| 2 |
Correct |
73 ms |
928 KB |
Output is correct |
| 3 |
Correct |
68 ms |
848 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
