제출 #1339220

#제출 시각아이디문제언어결과실행 시간메모리
1339220repmannCrossing (JOI21_crossing)C++20
26 / 100
215 ms29920 KiB
#include <bits/stdc++.h>
#define ll __int128
using namespace std;
int N, K, Q;
string S[4];
ll BASE, POW[200001], PS[200001];
char F['Z' + 1]['Z' + 1];
struct Node
{
  int l;
  ll h;
  char p;
}ST[(1 << 19) + 1];
void Merge(int i)
{
  ST[i].l = ST[i << 1].l + ST[i << 1 | 1].l;
  ST[i].h = ST[i << 1].h * POW[ST[i << 1 | 1].l] + ST[i << 1 | 1].h;
  return;
}
void Setup()
{
  K = 1;
  while(K < N) K <<= 1;
  for(int i = 0; i < N; i++) ST[i + K] = {1, S[3][i] - 'A' + 1, 0};
  for(int i = K - 1; i; i--) Merge(i);
  return;
}
void Propagate(int i)
{
  ST[i].h = (ST[i].p - 'A' + 1) * PS[ST[i].l - 1];
  if(i < K) ST[i << 1].p = ST[i << 1 | 1].p = ST[i].p;
  ST[i].p = 0;
  return;
}
void Update(int l, int r, char c, int i = 1, int lc = 1, int rc = K)
{
  if(ST[i].p) Propagate(i);
  if((l > rc) || (lc > r)) return;
  if((l <= lc) && (rc <= r)) {ST[i].p = c; return Propagate(i);}
  int s = (lc + rc) >> 1;
  Update(l, r, c, i << 1, lc, s);
  Update(l, r, c, i << 1 | 1, s + 1, rc);
  return Merge(i);
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> S[0] >> S[1] >> S[2] >> Q >> S[3];
  POW[0] = PS[0] = 1;
  POW[1] = BASE = 100003;
  for(int i = 2; i <= N; i++) POW[i] = POW[i - 1] * BASE;
  for(int i = 1; i <= N; i++) PS[i] = PS[i - 1] + POW[i];
  F['J']['J'] = F['O']['I'] = F['I']['O'] = 'J';
  F['O']['O'] = F['J']['I'] = F['I']['J'] = 'O';
  F['I']['I'] = F['J']['O'] = F['O']['J'] = 'I';
  set <ll> SET;
  auto Combine = [&](int p, int q, int r)
  {
    ll h = 0;
    char c;
    for(int i = 0; i < N; i++)
    {
      c = S[p][i];
      if(q >= 0) c = F[c][S[q][i]];
      if(r >= 0) c = F[c][S[r][i]];
      (h *= BASE) += c - 'A' + 1;
    }
    SET.insert(h);
  };
  Combine(0, -1, -1), Combine(1, -1, -1), Combine(2, -1, -1);
  Combine(0, 1, -1), Combine(0, 2, -1), Combine(1, 2, -1);
  Combine(0, 1, 2), Combine(0, 2, 1), Combine(1, 2, 0);
  Setup();
  cout << ((SET.find(ST[1].h) != SET.end()) ? "Yes\n" : "No\n");
  int l, r;
  char c;
  while(Q--)
  {
    cin >> l >> r >> c;
    Update(l, r, c);
    cout << ((SET.find(ST[1].h) != SET.end()) ? "Yes\n" : "No\n");
  }

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...