Submission #521545

#	Time	Username	Problem	Language	Result	Execution time	Memory
521545		Soumya1	Crossing (JOI21_crossing)	C++17	100 / 100	502 ms	18484 KiB

Main

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mod1 = 1e9 + 7;
const int mod2 = 10000019;
const int mxN = 2e5 + 5;
pair<int, int> p[mxN];
pair<int, int> pp[mxN];
vector<string> v;
vector<pair<int, int>> hsh;
pair<int, 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, 0});
  for (char c : s) {
    hsh.back().first = (3LL * hsh.back().first + eval(c)) % mod1;
    hsh.back().second = (3LL * hsh.back().second + eval(c)) % mod2;
  }
}
void build(int x, int lx, int rx) {
  if (lx == rx) {
    int c = eval(v[sz - 1][lx - 1]);
    t[x] = {c, c};
    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].first = ((1LL * t[x << 1].first * p[rx - mx].first) % mod1 + t[x << 1 | 1].first) % mod1;
  t[x].second = ((1LL * t[x << 1].second * p[rx - mx].second) % mod2 + t[x << 1 | 1].second) % mod2;
}
pair<int, int> calc(int c, int len) {
  return {(1LL * pp[len - 1].first * c) % mod1, (1LL * pp[len - 1].second * c) % mod2};
}
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].first = ((1LL * t[x << 1].first * p[rx - mx].first) % mod1 + t[x << 1 | 1].first) % mod1;
  t[x].second = ((1LL * t[x << 1].second * p[rx - mx].second) % mod2 + t[x << 1 | 1].second) % mod2;
}
void init(string a, string b, string c) {
  p[0] = {1, 1};
  for (int i = 1; i < mxN; i++) {
    p[i].first = (3LL * p[i - 1].first) % mod1;
    p[i].second = (3LL * p[i - 1].second) % mod2;
  }
  pp[0] = {1, 1};
  for (int i = 1; i < mxN; i++) {
    pp[i].first = (pp[i - 1].first + p[i].first) % mod1;
    pp[i].second = (pp[i - 1].second + p[i].second) % mod2;
  }
  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 (auto 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: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51