제출 #521538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521538		Soumya1	Crossing (JOI21_crossing)	C++17	0 / 100	77 ms	2512 KiB

Main

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 2e5 + 5;
int p[mxN];
int pp[mxN];
vector<string> v;
vector<int> hsh;
int t[4 * mxN];
int lazy[4 * mxN];
int sz;
int eval(char c) {
  if (c == 'I') return 0;
  if (c == 'O') return 1;
  return 2;
}
void hashh(string s) {
  hsh.push_back(0);
  for (char c : s) {
    hsh.back() = (3LL * hsh.back() + eval(c)) % mod;
  }
}
void build(int x, int lx, int rx) {
  if (lx == rx) {
    t[x] = eval(v[sz - 1][lx - 1]);
    lazy[x] = -1;
    return;
  }
  int mx = (lx + rx) >> 1;
  build(x << 1, lx, mx);
  build(x << 1 | 1, mx + 1, rx);
  lazy[x] = -1;
  t[x] = ((1LL * t[x << 1] * p[rx - mx]) % mod + t[x << 1 | 1]) % mod;
}
int calc(int c, int len) {
  return (1LL * pp[len - 1] * c) % mod;
}
void propagate(int x, int lx, int rx) {
  if (lx == rx) return;
  int mx = (lx + rx) >> 1;
  t[x << 1] = calc(lazy[x], mx - lx + 1);
  t[x << 1 | 1] = calc(lazy[x], rx - mx);
  lazy[x << 1] = lazy[x << 1 | 1] = lazy[x];
  lazy[x] = -1;
  return;
}
void update(int x, int lx, int rx, int l, int r, int c) {
  if (lazy[x] != -1) propagate(x, lx, rx);
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    t[x] = calc(c, rx - lx + 1);
    lazy[x] = c;
    return;
  }
  int mx = (lx + rx) >> 1;
  update(x << 1, lx, mx, l, r, c);
  update(x << 1 | 1, mx + 1, rx, l, r, c);
  t[x] = ((1LL * t[x << 1] * p[rx - mx]) % mod + t[x << 1 | 1]) % mod;
}
void init(string a, string b, string c) {
  p[0] = 1;
  for (int i = 1; i < mxN; i++) p[i] = (3LL * p[i - 1]) % mod;
  pp[0] = 1;
  for (int i = 1; i < mxN; i++) pp[i] = (pp[i - 1] + p[i]) % mod;
  map<string, bool> mp;
  v = {a, b, c};
  mp[a] = mp[b] = mp[c] = true;
  auto op = [&](string s, string tt) {
    string ret;
    for (int i = 0; i < (int) s.size(); i++) {
      if (s[i] == tt[i]) ret += s[i];
      else ret += ('I' ^ 'J' ^ 'O') ^ s[i] ^ tt[i];
    }
    return ret;
  };
  for (int i = 0; i < (int) v.size(); i++) {
    for (int j = i + 1; j < (int) v.size(); j++) {
      string ops = op(v[i], v[j]);
      if (!mp[ops]) {
        mp[ops] = true;
        v.push_back(ops);
      }
    }
  }
  for (string s : v) {
    hashh(s);
  }
  sz = v.size() + 1;
}
void query() {
  // cout << t[1] << endl;
  for (int i : hsh) {
    if (i == t[1]) {
      cout << "Yes\n";
      return;
    }
  }
  cout << "No\n";
}
void testCase() {
  int n;
  string a, b, c;
  cin >> n >> a >> b >> c;
  init(a, b, c);
  int q;
  string tt;
  cin >> q >> tt;
  v.push_back(tt);
  build(1, 1, n);
  query();
  // for (string s : v) cout << s << " "; cout << endl;
  // for (int i : hsh) cout << i << " "; cout << endl;
  while (q--) {
    int l, r;
    char cc;
    cin >> l >> r >> cc;
    update(1, 1, n, l, r, eval(cc));
    query();
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51