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;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
bool prime(int N) {
for (int i = 2; i * i <= N; ++i) {
if (N % i == 0) {
return 0;
}
}
return 1;
}
int rand_mod() {
int x = rand(1e9, 2e9);
while (!prime(x)) {
--x;
}
return x;
}
int rand_base() {
int x = rand(13, 999999);
while (!prime(x)) {
--x;
}
return x;
}
int n, q;
array<int, 3> MD{rand_mod(), rand_mod(), rand_mod()}, base{rand_base(), rand_base(), rand_base()};
array<int, 3> pw[N], pf[N], sum[N], s[4 * N];
int lz[4 * N];
map<array<int, 3>, bool> mp;
string S;
int add(int x, int y, int c) {
if ((x += y) >= MD[c]) {
x -= MD[c];
}
return x;
}
int conv(char c) {
return c == 'J' ? 1 : (c == 'O' ? 2 : 3);
}
void pull(int id, int l, int r) {
int md = (l + r) / 2;
for (int i = 0; i < 3; ++i) {
s[id][i] = add((long long) s[id * 2][i] * pw[r - md][i] % MD[i], s[id * 2 + 1][i], i);
}
}
void bld(int id = 1, int l = 1, int r = n) {
for (int i = 0; i < 3; ++i) {
sum[id][i] = pf[r - l][i];
}
if (l == r) {
int x = conv(S[l - 1]);
s[id] = {x, x, x};
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
pull(id, l, r);
}
void app(int id, int x) {
for (int i = 0; i < 3; ++i) {
s[id][i] = (long long) sum[id][i] * x % MD[i];
}
lz[id] = x;
}
void psh(int id) {
if (lz[id]) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
}
void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
app(id, x);
return;
}
psh(id);
int md = (l + r) / 2;
if (u <= md) {
upd(u, v, x, id * 2, l, md);
}
if (md < v) {
upd(u, v, x, id * 2 + 1, md + 1, r);
}
pull(id, l, r);
}
string cross(const string &a, const string &b) {
string res;
for (int i = 0; i < n; ++i) {
if (a[i] == b[i]) {
res += a[i];
} else {
for (auto c : {'J', 'O', 'I'}) {
if (c != a[i] && c != b[i]) {
res += c;
}
}
}
}
return res;
}
array<int, 3> get(const string &s) {
array<int, 3> h{};
for (char c : s) {
for (int i = 0; i < 3; ++i) {
h[i] = add((long long) h[i] * base[i] % MD[i], conv(c), i);
}
}
return h;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<string> st;
for (int i = 0; i < 3; ++i) {
string s; cin >> s;
st.push_back(s);
mp[get(s)] = 1;
}
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
auto mix = cross(st[i], st[j]);
auto h = get(mix);
if (!mp.count(h)) {
mp[h] = 1;
st.push_back(mix);
}
}
}
bool flg = 1;
while (flg) {
flg = 0;
for (int i = 0; i + 1 < st.size(); ++i) {
auto mix = cross(st[i], st.back());
auto h = get(mix);
if (!mp.count(h)) {
st.push_back(mix);
mp[h] = 1;
flg = 1;
break;
}
}
}
for (auto it : {0, 1, 2}) {
pw[0][it] = pf[0][it] = 1;
for (int i = 1; i <= n; ++i) {
pw[i][it] = (long long) pw[i - 1][it] * base[it] % MD[it];
pf[i][it] = add(pf[i - 1][it], pw[i][it], it);
}
}
cin >> q >> S;
bld();
auto qry = [&]() {
cout << (mp.count(s[1]) ? "Yes" : "No") << "\n";
};
qry();
while (q--) {
int l, r; char c; cin >> l >> r >> c;
upd(l, r, conv(c));
qry();
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for (int i = 0; i + 1 < st.size(); ++i) {
| ~~~~~~^~~~~~~~~~~
# | 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... |