| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1239292 | faruk | Crossing (JOI21_crossing) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef __uint128_t ll;
typedef pair<ll, ll> pii;
const ll P1 = 23;
const LL P2 = 31;
const ll mod2 = 1e9 + 7;
const ll mod1 = 1e9 + 9;
const ll maxn = 3e5;
ll merge(ll l, ll r, ll v1, ll v2, ll mod, vector<ll> &powp) {
return ((powp[r - l + 1] * v2) % mod + v1) % mod;
}
map<char, ll> trans = {{'J', 43}, {'O', 39}, {'I', 53}};
struct seggy {
ll mod;
ll n, P;
vector<ll> seg, lazy, powp, csum;
seggy() {}
seggy(ll n, ll mod, ll P) : P(P), mod(mod), n(n), seg(vector<ll>(4 * n)), lazy(vector<ll>(4 * n)) {
powp = csum = vector<ll>(maxn, 1);
for (ll i = 1; i < maxn; i++)
powp[i] = powp[i - 1] * P % mod;
csum[0] = 0;
for (ll i = 2; i < maxn; i++)
csum[i] = (csum[i - 1] + powp[i - 1]) % mod;
}
void push(ll l, ll r, ll idx) {
if (lazy[idx] == 0)
return;
seg[idx] = csum[r - l + 1] * lazy[idx] % mod;
if (l != r)
lazy[idx * 2] = lazy[idx * 2 + 1] = lazy[idx];
lazy[idx] = 0;
}
void upd(ll l, ll r, ll L, ll R, ll idx, ll val) {
push(l, r, idx);
if (l >= L and r <= R) {
lazy[idx] = val;
push(l, r, idx);
return;
}
if (l > R || r < L)
return;
ll mid = (l + r) / 2;
upd(l, mid, L, R, idx * 2, val);
upd(mid + 1, r, L, R, idx * 2 + 1, val);
seg[idx] = merge(l, mid, seg[idx * 2], seg[idx * 2 + 1], mod, powp);
}
void upd(ll l, ll r, ll val) {
upd(0, n - 1, l, r, 1, val);
}
ll query() {
push(0, n - 1, 1);
return seg[1];
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<string> s(3);
for (ll i = 0; i < 3; i++)
cin >> s[i];
vector<bool> forced(n, true);
for (ll i = 0; i < n; i++)
{
if (s[0][i] != s[1][i] || s[0][i] != s[2][i] || s[1][i] != s[2][i])
forced[i] = false;
}
vector<ll> cmp(n);
vector<vector<ll>> per(4);
/*
0, 1 and 2 are diff
1, 0 and 2 are diff
2, 0 and 1 are diff
3 all are diff
*/
for (ll i = 0; i < n; i++)
{
if (forced[i])
continue;
set<char> s1;
for (ll k = 0; k < 3; k++)
s1.insert(s[k][i]);
if (s1.size() == 3)
per[3].push_back(i), cmp[i] = 3;
else {
for (ll j = 0; j < 3; j++)
{
bool ok = true;
for (ll k = 0; k < 3; k++)
if (j != k and s[j][i] == s[k][i])
ok = false;
if (ok)
per[j].push_back(i), cmp[i] = j;
}
}
}
ll num_comps = 0;
vector<vector<char>> variants(3, vector<char>(n));
for (vector<ll> ids : per)
{
if (!ids.empty())
num_comps++;
for (ll i : ids)
{
variants[0][i] = s[0][i], variants[1][i] = s[1][i], variants[2][i] = s[2][i];
for (ll j = 0; j < 3; j++)
{
bool can_change = false;
for (ll k = 0; k < 3; k++)
if (j != k and variants[j][i] == variants[k][i])
can_change = true;
if (!can_change)
continue;
char me = 'J' + 'O' + 'I';
for (ll k = 0; k < 3; k++)
if (j != k)
me -= variants[k][i];
variants[j][i] = me;
break;
}
}
}
seggy seg1(n, mod1, P1), seg2(n, mod2, P2);
set<ll> poss1, poss2;
for (ll i = 0; i < 3; i++) {
for (ll j = 0; j < 3; j++) {
for (ll k = 0; k < 3; k++) {
for (ll l = 0; l < 3; l++) {
string I = "";
for (ll t = 0; t < n; t++)
{
if (forced[t])
I += s[0][t];
else if (cmp[t] == 0)
I += variants[i][t];
else if (cmp[t] == 1)
I += variants[j][t];
else if (cmp[t] == 2)
I += variants[k][t];
else if (cmp[t] == 3)
I += variants[l][t];
}
ll hsh = 0;
for (ll t = 0; t < n; t++)
hsh = (hsh + (trans[I[t]] * seg1.powp[t] % mod1)) % mod1;
poss1.insert(hsh);
hsh = 0;
for (ll t = 0; t < n; t++)
hsh = (hsh + (trans[I[t]] * seg2.powp[t] % mod2)) % mod2;
poss2.insert(hsh);
}
}
}
}
string t;
int q;
cin >> q;
cin >> t;
for (ll i = 0; i < n; i++)
{
seg1.upd(i, i, trans[t[i]]);
seg2.upd(i, i, trans[t[i]]);
}
for (ll Q = 0; Q <= q; Q++)
{
if (Q > 0)
{
int l, r;
cin >> l >> r;
char c;
cin >> c;
seg1.upd(l - 1, r - 1, trans[c]);
seg2.upd(l - 1, r - 1, trans[c]);
}
if (poss1.count(seg1.query()) and poss2.count(seg2.query()))
cout << "Yes\n";
else
cout << "No\n";
}
}