Submission #420201

#	Time	Username	Problem	Language	Result	Execution time	Memory
420201		rama_pang	Crossing (JOI21_crossing)	C++17	100 / 100	1965 ms	42032 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const array<int, 4> MOD = {
  1000000007,
  1000000009,
  998244353,
  420691273,
};

const array<int, 4> KEY = {
  7,
  37,
  67,
  97,
};

class SegTree {
 public:
  int sz;
  vector<int> len;
  vector<int> lazy;
  vector<array<int, 4>> power;
  vector<array<array<int, 4>, 4>> hashes;

  SegTree(int sz, vector<int> A) : sz(sz) {
    power.resize(sz + 1);
    power[0] = {1, 1, 1, 1};
    for (int i = 1; i <= sz; i++) {
      for (int j = 0; j < 4; j++) {
        power[i][j] = 1ll * power[i - 1][j] * KEY[j] % MOD[j];
      }
    }

    len.resize(2 * sz);
    lazy.resize(2 * sz);
    hashes.resize(2 * sz);
    Build(1, 0, sz - 1, A);
  }

  array<int, 4> Merge(array<int, 4> a, array<int, 4> b, int lena) {
    array<int, 4> c;
    for (int i = 0; i < 4; i++) {
      c[i] = (1ll * a[i] + 1ll * b[i] * power[lena][i]) % MOD[i];
    }
    return c;
  }

  void Set(int n, int x) {
    assert(1 <= x && x <= 3);
    hashes[n][0] = hashes[n][x];
    lazy[n] = x;
  }

  void Push(int n, int lc, int rc) {
    if (lazy[n]) {
      Set(lc, lazy[n]);
      Set(rc, lazy[n]);
      lazy[n] = 0;
    }
  }

  void Build(int n, int tl, int tr, const vector<int> &A) {
    if (tl == tr) {
      len[n] = 1;
      for (int x = 0; x < 4; x++) {
        for (int j = 0; j < 4; j++) {
          hashes[n][x][j] = 1ll * (x == 0 ? (A[tl] + 1) : x) * KEY[j] % MOD[j];
        }
      }
      return;
    }
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Build(n + 1, tl, md, A);
    Build(z, md + 1, tr, A);
    len[n] = len[n + 1] + len[z];
    for (int x = 0; x < 4; x++) {
      hashes[n][x] = Merge(hashes[n + 1][x], hashes[z][x], len[n + 1]);
    }
  }

  void RangeSet(int n, int tl, int tr, int l, int r, int x) {
    if (tl > r || l > tr || tl > tr || l > r) return;
    if (l <= tl && tr <= r) return Set(n, x);
    int md = (tl + tr) / 2;
    int z = n + 2 * (md - tl + 1);
    Push(n, n + 1, z);
    RangeSet(n + 1, tl, md, l, r, x);
    RangeSet(z, md + 1, tr, l, r, x);
    hashes[n][0] = Merge(hashes[n + 1][0], hashes[z][0], len[n + 1]);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

  int N;
  cin >> N;
  vector<vector<int>> S(3);
  for (int i = 0; i < 3; i++) {
    string s;
    cin >> s;
    for (auto x : s) {
      if (x == 'J') S[i].push_back(0);
      if (x == 'O') S[i].push_back(1);
      if (x == 'I') S[i].push_back(2);
    }
  }
  while (true) {
    sort(begin(S), end(S));
    S.resize(unique(begin(S), end(S)) - begin(S));
    bool foundNew = false;
    for (auto x : S) if (!foundNew) {
      for (auto y : S) if (!foundNew) {
        vector<int> res;
        for (int i = 0; i < N; i++) {
          if (x[i] == y[i]) {
            res.push_back(x[i]);
          } else {
            for (int c = 0; c < 3; c++) {
              if (x[i] != c && y[i] != c) {
                res.push_back(c);
              }
            }
          }
        }
        if (!binary_search(begin(S), end(S), res)) {
          S.push_back(res);
          foundNew = true;
        }
      }
    }
    if (!foundNew) {
      break;
    }
  }

  assert(S.size() <= 9);
  vector<array<int, 4>> hashS;
  for (auto s : S) {
    hashS.push_back(SegTree(N, s).hashes[1][0]);
  }

  int Q;
  cin >> Q;

  vector<int> T;
  {
    string s;
    cin >> s;
    for (auto x : s) {
      if (x == 'J') T.push_back(0);
      if (x == 'O') T.push_back(1);
      if (x == 'I') T.push_back(2);
    }
  }

  SegTree seg(N, T);

  for (int q = 0; q <= Q; q++) {
    if (q > 0) {
      int l, r, x;
      char c;
      cin >> l >> r >> c;
      l--, r--;
      if (c == 'J') x = 1;
      if (c == 'O') x = 2;
      if (c == 'I') x = 3;
      seg.RangeSet(1, 0, N - 1, l, r, x);
    }
    bool ans = false;
    for (auto s : hashS) {
      if (s == seg.hashes[1][0]) {
        ans = true;
        break;
      }
    }
    if (ans) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:173:19: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  173 |       seg.RangeSet(1, 0, N - 1, l, r, x);
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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