#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace std;
using namespace __gnu_pbds;
#define LL long long
#define pLL pair<long long, long long>
#define F first
#define S second
#define pb push_back
#define rz resize
#define all(x) x.begin(), x.end()
#define endl '\n'
void Star_Brust_Stream()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
return;
}
const LL INF = 1e18, MOD = 341036447;
vector<LL> meee, pre;
vector<LL> tar;
struct seg
{
LL l, r, v, m, lz;
seg *ln, *rn;
seg(LL ll, LL rr) : l(ll), r(rr)
{
lz = -1;
m = (l + r) >> 1;
if (l != r - 1)
{
ln = new seg(l, m);
rn = new seg(m, r);
v = comb(ln->v, rn->v);
}
else
{
v = tar[l];
}
return;
}
LL comb(LL a, LL b)
{
return (((b * meee[r - m - 1]) % MOD) + a) % MOD;
}
LL rv()
{
if (lz == -1)
{
return v;
}
return (lz * pre[(r - l-1)]) % MOD;
}
void push()
{
if (lz != -1)
{
ln->lz = lz;
rn->lz = lz;
v = rv();
lz = -1;
}
}
LL ask(LL ll, LL rr)
{
if (l == ll && r == rr)
{
return rv() % MOD;
}
push();
if (m >= rr)
{
return ln->ask(ll, rr) % MOD;
}
else if (m <= ll)
{
return rn->ask(ll, rr) % MOD;
}
else
{
return comb(ln->ask(ll, m), rn->ask(m, rr));
}
}
void revise(LL ll, LL rr, LL num)
{
if (l == ll && r == rr)
{
lz = num;
return;
}
else
{
push();
LL m = (l + r) >> 1;
if (m >= rr)
{
ln->revise(ll, rr, num);
}
else if (m <= ll)
{
rn->revise(ll, rr, num);
}
else
{
ln->revise(ll, m, num);
rn->revise(m, rr, num);
}
v = comb(ln->rv(), rn->rv());
}
}
};
int main()
{
Star_Brust_Stream();
meee.rz(2e5 + 10);
pre.rz(2e5 + 10);
meee[0] = 1;
pre[0] = 1;
for (int i = 1; i < meee.size(); i++)
{
meee[i] = (meee[i - 1] * 197) % MOD;
pre[i] = (pre[i - 1] + meee[i]) % MOD;
}
set<string> ne;
set<LL> s;
LL n;
cin >> n;
vector<string> vs(3);
for (int i = 0; i < 3; i++)
{
cin >> vs[i];
ne.insert(vs[i]);
}
for (int i = 0; i < 3; i++)
{
LL h = 0;
for (int j = 0; j < n; j++)
{
h = (h * 197) % MOD;
h = (h + vs[i][j]) % MOD;
}
s.insert(h);
}
LL x[3] = {0, 1, 2};
LL y[3] = {1, 2, 0};
for (int i = 0; i < 3; i++)
{
string re;
for (int j = 0; j < n; j++)
{
if (vs[x[i]][j] == vs[y[i]][j])
{
re += vs[x[i]][j];
}
else
{
set<char> c;
c.insert('J');
c.insert('O');
c.insert('I');
c.erase(vs[x[i]][j]);
c.erase(vs[y[i]][j]);
re += *c.begin();
}
}
LL h = 0;
for (int j = 0; j < n; j++)
{
h = (h * 197) % MOD;
h = (h + re[j]) % MOD;
}
ne.insert(re);
s.insert(h);
}
for (string str : ne)
{
string re;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < n; j++)
{
if (str[j] == vs[i][j])
{
re += vs[i][j];
}
else
{
set<char> c;
c.insert('J');
c.insert('O');
c.insert('I');
c.erase(vs[i][j]);
c.erase(str[j]);
re += *c.begin();
}
}
LL h = 0;
for (int j = 0; j < n; j++)
{
h = (h * 197) % MOD;
h = (h + re[j]) % MOD;
}
s.insert(h);
}
}
LL q;
cin >> q;
string t;
cin >> t;
tar.rz(n);
for (int i = 0; i < n; i++)
{
tar[i] = t[i];
}
seg st(0, n);
if (s.count(st.rv()))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
while (q--)
{
LL a, b;
char c;
cin >> a >> b >> c;
a--;
st.revise(a, b, c);
if (s.count(st.rv()))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
// system("pause");
return 0;
}
/*
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 1; i < meee.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
3884 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3976 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
4036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
3884 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3976 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
4036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
3884 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3976 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
4036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
3884 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
79 ms |
3976 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
4036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
