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>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e6 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 1337;
int n, Q;
ll pw[N], hs[30][N];
void initHS () {
pw[0] = 1;
rep (i, 1, n * 2) pw[i] = pw[i - 1] * BASE;
rep (i, 0, 29) hs[i][0] = 1;
vector<char> c = {'J', 'O', 'I'};
rep (i, 1, n)
iter (id, c)
hs[id - 'A'][i] = (hs[id - 'A'][i - 1] * BASE % Mod + id - 'A') % Mod;
}
ll getHS (string S) {
ll res = 0;
rep (i, 1, n) res = (res * BASE % Mod + S[i - 1] - 'A') % Mod;
return res;
}
void solution () {
cin >> n;
string A, B, C;
cin >> A >> B >> C;
vector<char> c = {'J', 'O', 'I'};
set<string> S = {A, B, C};
auto Merge = [] (string A, string B) {
static string res;
res.resize(SZ(A));
rep (i, 0, SZ(A) - 1)
if (A[i] == B[i]) res[i] = A[i];
else {
static set<char> c;
c = {'J', 'O', 'I'};
c.erase(A[i]);
c.erase(B[i]);
res[i] = *c.begin();
}
return res;
};
int prevsz = SZ(S);
while (1) {
static set<string> newStr;
newStr.clear();
iter (&id1, S)
iter( &id2, S) newStr.insert(Merge(id1, id2));
iter (&id, newStr) S.insert(id);
if (SZ(S) == prevsz) break;
else prevsz = SZ(S);
}
set<ll> vecHS;
initHS();
iter (&id, S) vecHS.insert(getHS(id));
cin >> Q;
string T; cin >> T;
if (vecHS.find(getHS(T)) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
rep (i, 1, Q) {
int L, R;
char C;
cin >> L >> R >> C;
rep (j, L - 1, R - 1) T[j] = char(C);
if (vecHS.find(getHS(T)) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13
*/
# | 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... |