This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* author: NimaAryan
* created: 2023-12-01 12:26:57
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
constexpr i64 M = 1E9 + 7;
constexpr i64 B = 28463;
vector<i64> powB{1};
vector<vector<i64>> hashC(26);
void init() {
while (powB.size() < 3E5) {
powB.push_back(powB.back() * B % M);
}
for (int i = 0; i < 26; ++i) {
hashC[i].push_back(0);
while (hashC[i].size() < 3E5) {
hashC[i].push_back((hashC[i].back() * B + ('A' + i)) % M);
}
}
}
struct Tag {
char ch = '?';
void apply(const Tag& v) {
if (v.ch != '?') {
ch = v.ch;
}
}
};
struct Info {
int len = 0;
i64 hash = 0;
void apply(int l, int r, const Tag& v) {
if (v.ch != '?') {
len = r - l;
hash = hashC[v.ch - 'A'][len];
}
}
};
Info operator+(Info a, Info b) {
Info res;
res.len = a.len + b.len;
res.hash = (a.hash * powB[a.len] % M + b.hash) % M;
return res;
}
class SegmentTree {
public:
int n;
vector<Info> info;
vector<Tag> tag;
SegmentTree(int n) : n(n) {
info.assign(4 << __lg(n), Info());
tag.assign(4 << __lg(n), Tag());
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, int l, int r, const Tag& v) {
info[p].apply(l, r, v);
tag[p].apply(v);
}
void push(int p, int l, int r) {
int m = (l + r) / 2;
apply(2 * p, l, m, tag[p]);
apply(2 * p + 1, m, r, tag[p]);
tag[p] = Tag();
}
void range_apply(int p, int l, int r, int lx, int rx, const Tag& v) {
if (l >= rx || r <= lx) {
return;
}
if (l >= lx && r <= rx) {
apply(p, l, r, v);
return;
}
push(p, l, r);
int m = (l + r) / 2;
range_apply(2 * p, l, m, lx, rx, v);
range_apply(2 * p + 1, m, r, lx, rx, v);
pull(p);
}
void range_apply(int lx, int rx, const Tag& v) {
range_apply(1, 0, n, lx, rx, v);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int N;
cin >> N;
vector<string> S(3);
for (int i = 0; i < 3; ++i) {
cin >> S[i];
}
set<string> a;
for (int i = 0; i < 3; ++i) {
a.insert(S[i]);
}
while (true) {
auto new_a = a;
for (string s : a) {
for (string t : a) {
if (s != t) {
string u;
for (int i = 0; i < N; ++i) {
if (s[i] == t[i]) {
u.push_back(s[i]);
} else {
set<char> rb{'J', 'O', 'I'};
rb.erase(s[i]);
rb.erase(t[i]);
u.push_back(*rb.begin());
}
}
if (!new_a.count(u)) {
new_a.insert(u);
}
}
}
}
if (a == new_a) {
break;
}
a.swap(new_a);
}
set<i64> search;
for (string s : a) {
i64 hash = 0;
for (int i = 0; i < N; ++i) {
hash = (hash * B + s[i]) % M;
}
search.insert(hash);
}
int Q;
cin >> Q;
string T;
cin >> T;
SegmentTree seg(N);
for (int i = 0; i < N; ++i) {
seg.range_apply(i, i + 1, Tag{T[i]});
}
i64 hash = seg.info[1].hash;
if (search.count(hash)) {
cout << "Yes" << "\n";
} else {
cout << "No" << "\n";
}
while (Q--) {
int L, R;
cin >> L >> R;
--L;
char C;
cin >> C;
seg.range_apply(L, R, Tag{C});
i64 hash = seg.info[1].hash;
if (search.count(hash)) {
cout << "Yes" << "\n";
} else {
cout << "No" << "\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |