Submission #881569

#	Time	Username	Problem	Language	Result	Execution time	Memory
881569		nima_aryan	Crossing (JOI21_crossing)	C++17	100 / 100	2013 ms	122900 KiB

Main

/**
 *    author:  NimaAryan
 *    created: 2023-12-01 12:26:57  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 M = 1E9 + 7;
constexpr i64 B = 28463;

vector<i64> powB{1};
vector<vector<i64>> hashC(26);

void init() {
  while (powB.size() < 3E5) {
    powB.push_back(powB.back() * B % M);
  }
  for (int i = 0; i < 26; ++i) {
    hashC[i].push_back(0);
    while (hashC[i].size() < 3E5) {
      hashC[i].push_back((hashC[i].back() * B + ('A' + i)) % M);
    }
  }
}

struct Tag {
  char ch = '?';

  void apply(const Tag& v) {
    if (v.ch != '?') {
      ch = v.ch;
    }
  }
};
struct Info {
  int len = 0;
  i64 hash = 0;

  void apply(int l, int r, const Tag& v) {
    if (v.ch != '?') {
      len = r - l;
      hash = hashC[v.ch - 'A'][len];
    }
  }
};
Info operator+(Info a, Info b) {
  Info res;
  res.len = a.len + b.len;
  res.hash = (a.hash * powB[b.len] % M + b.hash) % M;
  return res;
}

class SegmentTree {
 public:
  int n;
  vector<Info> info;
  vector<Tag> tag;

  SegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }

  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, int l, int r, const Tag& v) {
    info[p].apply(l, r, v);
    tag[p].apply(v);
  }
  void push(int p, int l, int r) {
    int m = (l + r) / 2;
    apply(2 * p, l, m, tag[p]);
    apply(2 * p + 1, m, r, tag[p]);
    tag[p] = Tag();
  }

  void range_apply(int p, int l, int r, int lx, int rx, const Tag& v) {
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, l, r, v);
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    range_apply(2 * p, l, m, lx, rx, v);
    range_apply(2 * p + 1, m, r, lx, rx, v);
    pull(p);
  }
  void range_apply(int lx, int rx, const Tag& v) {
    range_apply(1, 0, n, lx, rx, v);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  init();

  int N;
  cin >> N;

  vector<string> S(3);
  for (int i = 0; i < 3; ++i) {
    cin >> S[i];
  }

  set<string> a;
  for (int i = 0; i < 3; ++i) {
    a.insert(S[i]);
  }
  while (true) {
    auto new_a = a;
    for (string s : a) {
      for (string t : a) {
        if (s != t) {
          string u;
          for (int i = 0; i < N; ++i) {
            if (s[i] == t[i]) {
              u.push_back(s[i]);
            } else {
              set<char> rb{'J', 'O', 'I'};
              rb.erase(s[i]);
              rb.erase(t[i]);
              u.push_back(*rb.begin());
            }
          }
          if (!new_a.count(u)) {
            new_a.insert(u);
          }
        }
      }
    }
    if (a == new_a) {
      break;
    }
    a.swap(new_a);
  }

  set<i64> search;
  for (string s : a) {
    i64 hash = 0;
    for (int i = 0; i < N; ++i) {
      hash = (hash * B + s[i]) % M;
    }
    search.insert(hash);
  }

  int Q;
  cin >> Q;

  string T;
  cin >> T;

  SegmentTree seg(N);
  for (int i = 0; i < N; ++i) {
    seg.range_apply(i, i + 1, Tag{T[i]});
  }

  i64 hash = seg.info[1].hash;
  if (search.count(hash)) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }

  while (Q--) {
    int L, R;
    cin >> L >> R;
    --L;
    char C;
    cin >> C;
    seg.range_apply(L, R, Tag{C});
    i64 hash = seg.info[1].hash;
    if (search.count(hash)) {
      cout << "Yes" << "\n";
    } else {
      cout << "No" << "\n";
    }
  }

  return 0;
}

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