Submission #1163372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163372		fryingduc	Crossing (JOI21_crossing)	C++20	100 / 100	409 ms	17964 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int base = 31;
const int mod = 1e9 + 9;
int p[maxn];
int n, q;
string sa, sb, sc, t;
int hc[4][maxn];

string crossing(string x, string y) {
  string t;
  for (int i = 0; i < n; ++i) {
    if (x[i] == y[i]) t += x[i];
    else {
      if (x[i] != 'J' and y[i] != 'J') t += 'J';
      else if (x[i] != 'O' and y[i] != 'O') t += 'O';
      else t += 'I';
    }
  }
  return t;
}

int convert(char c) {
  if (c == 'J') return 1;
  if (c == 'O') return 2;
  if (c == 'I') return 3;
  return -1;
}

int build_hash(string s) {
  reverse(s.begin(), s.end());
  int h = 0;
  for (int i = 0; i < (int)s.size(); ++i) {
    (h = 1ll * h * base % mod + convert(s[i])) %= mod;
  }
  return h;
}

struct node {
  int val, len;
  
  node() { val = len = 0; }
  
  node (int val, int len) : val(val), len(len) {}
  
  node operator+(const node &o) const {
    node res = o;
    res.val = 1ll * res.val * p[len] % mod;
    res.val = res.val + val;
    if (res.val >= mod) res.val -= mod;
    res.len += len;
    return res;
  }
  
} tree[maxn << 2];
int lazy[maxn << 2];

void build(int ind = 1, int l = 1, int r = n) {
  if (l == r) {
    tree[ind] = node(convert(t[l - 1]), 1);
    return;
  }
  int mid = (l + r) >> 1;
  build(ind << 1, l, mid);
  build(ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

void down(int ind, int l, int r) {
  tree[ind].val = hc[lazy[ind]][r - l + 1];
  if (l != r) {
    lazy[ind << 1] = lazy[ind << 1 | 1] = lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, int val, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] = val;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, val, ind << 1, l, mid);
  update(x, y, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

int get() {
  if (lazy[1]) down(1, 1, n);
  return tree[1].val;
}

void solve() {
  cin >> n >> sa >> sb >> sc;
  set<string> s;
  s.insert(sa);
  s.insert(sb);
  s.insert(sc);
  set<string> ns;
  while (true) {
    for (auto i:s) {
      for (auto j:s) {
        if (i == j) continue;
        ns.insert(crossing(i, j));
      }
    }
    bool flag = 0;
    for (auto i:ns) {
      if (!s.count(i)) {
        flag = 1;
        s.insert(i);
      }
    }
    if (!flag) break;
    ns.clear();
  }
  vector<int> vcl;
  for (auto &i:s) {
//    debug(i, build_hash(i));
    vcl.push_back(build_hash(i));
  }
  for (int x = 1; x <= 3; ++x) {
    for (int i = 1; i <= n; ++i) {
      (hc[x][i] = 1ll * hc[x][i - 1] * base % mod + x) %= mod;
    }
  }
  cin >> q >> t;
  build();
  bool f = 0;
  for (auto i:vcl) {
    if (get() == i) {
      f = 1;
      break;
    }
  }
  cout << (f ? "Yes\n" : "No\n");
  while (q--) {
    int l, r; char c; cin >> l >> r >> c;
    update(l, r, convert(c));
    int cur = get();
    f = 0;
    for (auto i:vcl) {
      if (cur == i) {
        f = 1;
        break;
      }
    }
    cout << (f ? "Yes\n" : "No\n");
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  p[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    p[i] = 1ll * p[i - 1] * base % mod;
  }
  solve();

  return 0;
}

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