#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int ll
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
uniform_int_distribution<ll> uid(l, r);
return uid(rng);
}
int pr[maxn][3], seg[4*maxn], lz[4*maxn];
void push(int i, int l, int r) {
if (lz[i] == 3) return;
seg[i] = pr[r][lz[i]] ^ pr[l-1][lz[i]];
if (l != r) lz[2*i] = lz[2*i+1] = lz[i];
lz[i] = 3;
}
void upd(int i, int l, int r, int x, int y, int k) {
push(i, l, r);
if (r < x || y < l) return;
if (x <= l && r <= y) {
lz[i] = k;
push(i, l, r);
return;
}
int md = (l + r) / 2;
upd(2*i, l, md, x, y, k), upd(2*i+1, md+1, r, x, y, k);
seg[i] = seg[2*i] ^ seg[2*i+1];
}
int32_t main(){_
int n; cin >> n; string a, b, c; cin >> a >> b >> c;
// there are only 27 strings that can be generated (trust)
map<char, int> f;
f['J'] = 2;
f['O'] = 0;
f['I'] = 1;
for (int i = 0; i < 3; ++i) {
for (int j = 1; j <= n; ++j) {
pr[j][i] = pr[j-1][i] ^ rnd(0, 8e18);
}
}
map<int, bool> existe;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
int x = 0;
if (i + j + k == 0) continue;
for (int w = 1; w <= n; ++w) {
int ac = f[a[w-1]], bc = f[b[w-1]], cc = f[c[w-1]];
int res = (ac * i + bc * j + cc * k) % 3;
x ^= pr[w][res] ^ pr[w-1][res];
}
existe[x] = 1;
}
}
}
for (int i = 1; i <= 4 * n; ++i) lz[i] = 3;
int q; cin >> q;
string t; cin >> t;
for (int i = 1; i <= n; ++i) upd(1, 1, n, i, i, f[t[i-1]]);
cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;
while (q--) {
int l, r; char c; cin >> l >> r >> c;
upd(1, 1, n, l, r, f[c]);
cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
107 ms |
11692 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
107 ms |
11692 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
107 ms |
11692 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
107 ms |
11692 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |