This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string cross(string &a, string &b) {
string res(a.size(), 'a');
for (int i = 0; i < a.size(); ++i) {
if (a[i] == b[i]) {
res[i] = a[i];
} else {
res[i] = 'J' ^ 'O' ^ 'I' ^ a[i] ^ b[i];
}
}
return res;
}
constexpr int MOD[]{1000'000'000 + 7, 228228227, 998244353};
constexpr int P = 239, hsz = size(MOD);
constexpr int N = 2e5 + 1;
struct Info {
array<int, hsz> h{}, power{}, sum{};
Info() = default;
};
vector<Info> t;
vector<int> tag;
int sz;
void apply(int x, int y) {
if (y != -1) {
for (int i = 0; i < hsz; ++i) {
t[x].h[i] = 1LL * t[x].sum[i] * y % MOD[i];
}
tag[x] = y;
}
}
void push(int x) {
apply(x << 1, tag[x]);
apply(x << 1 | 1, tag[x]);
tag[x] = -1;
}
void pull(int x) {
for (int i = 0; i < hsz; ++i) {
t[x].h[i] = (t[x << 1].h[i] + 1LL * t[x << 1].power[i] * P % MOD[i] * t[x << 1 | 1].h[i]) % MOD[i];
t[x].power[i] = 1LL * t[x << 1].power[i] * t[x << 1 | 1].power[i] % MOD[i] * P % MOD[i];
t[x].sum[i] = (t[x << 1].sum[i] + 1LL * t[x << 1].power[i] * P % MOD[i] * t[x << 1 | 1].sum[i]) % MOD[i];
}
}
int to_int(char c) {
return c == 'J' ? 1 : 1 + (c == 'O');
}
void init(int n, string T) {
sz = 1 << __lg(n) + bool(n & (n - 1));
tag.assign(sz << 1, -1), t.resize(sz << 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < hsz; ++j) {
t[i + sz].sum[j] = t[i + sz].power[j] = 1;
t[i + sz].h[j] = to_int(T[i]);
}
}
for (int i = sz - 1; i > 0; --i) {
pull(i);
}
}
void rangeApply(int l, int r, int tg, int x = 1, int lx = 0, int rx = sz) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
apply(x, tg);
return;
}
push(x);
int mid = (lx + rx) >> 1;
rangeApply(l, r, tg, x << 1, lx, mid), rangeApply(l, r, tg, x << 1 | 1, mid, rx);
pull(x);
}
array<int, hsz> hashed(string &s) {
array<int, hsz> ans{};
for (int i = int(s.size()) - 1; i >= 0; --i) {
for (int j = 0; j < hsz; ++j) {
ans[j] = (1LL * ans[j] * P + to_int(s[i])) % MOD[j];
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string A, B, C;
cin >> A >> B >> C;
unordered_set<string> every{A, B, C};
queue<string> qu;
qu.push(A), qu.push(B), qu.push(C);
while (!qu.empty()) {
string s = qu.front();
qu.pop();
for (string to : every) {
string res = cross(s, to);
if (!every.count(res)) {
qu.push(res);
every.insert(res);
}
}
}
set<array<int, hsz>> st;
for (string s : every) {
st.insert(hashed(s));
}
int q;
cin >> q;
string T;
cin >> T;
init(n, T);
cout << (st.count(t[1].h) ? "Yes\n" : "No\n");
while (q--) {
int l, r;
char c;
cin >> l >> r >> c;
rangeApply(l - 1, r, to_int(c));
for (int i = l - 1; i < r; ++i) {
T[i] = c;
}
assert(t[1].h == hashed(T));
assert((hashed(T) == hashed(A)) == (A == T));
cout << (st.count(t[1].h) ? "Yes\n" : "No\n");
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'std::string cross(std::string&, std::string&)':
Main.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for (int i = 0; i < a.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp: In function 'void init(int, std::string)':
Main.cpp:61:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
61 | sz = 1 << __lg(n) + bool(n & (n - 1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |