Submission #684446

#	Time	Username	Problem	Language	Result	Execution time	Memory
684446		peijar	Crossing (JOI21_crossing)	C++17	100 / 100	417 ms	50364 KiB

Main

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

using H = pair<int, int>;

H add(H a, H b) {
  a.first += b.first;
  if (a.first >= MOD1)
    a.first -= MOD1;
  a.second += b.second;
  if (a.second >= MOD2)
    a.second -= MOD2;
  return a;
}

H sub(H a, H b) {
  a.first -= b.first;
  a.second -= b.second;
  if (a.first < 0)
    a.first += MOD1;
  if (a.second < 0)
    a.second += MOD2;
  return a;
}

H mult(H a, H b) {
  return pair(a.first * b.first % MOD1, a.second * b.second % MOD2);
}

const int MAXN = 1e6;

const int BASE = 315;

H pows[MAXN];
int iDeb[MAXN], iFin[MAXN];
H sumPows[MAXN], rangeHash[MAXN];
int lazy[MAXN];

void pull(int node) {
  sumPows[node] = add(sumPows[2 * node], sumPows[2 * node + 1]);
  rangeHash[node] = add(rangeHash[2 * node], rangeHash[2 * node + 1]);
}

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  lazy[node] = -1;

  if (l == r) {
    sumPows[node] = pows[l];
    return;
  }
  int m = (l + r) / 2;
  build(2 * node, l, m);
  build(2 * node + 1, m + 1, r);
  pull(node);
}

void push(int node) {
  if (lazy[node] == -1)
    return;
  int x = lazy[node];
  lazy[node] = -1;

  rangeHash[node] = mult(pair(x, x), sumPows[node]);
  if (iDeb[node] < iFin[node])
    lazy[2 * node] = lazy[2 * node + 1] = x;
}

void rangeSet(int node, int l, int r, int x) {
  push(node);
  if (l > iFin[node] or r < iDeb[node])
    return;
  if (l <= iDeb[node] and iFin[node] <= r) {
    lazy[node] = x;
    push(node);
    return;
  }

  rangeSet(2 * node, l, r, x);
  rangeSet(2 * node + 1, l, r, x);
  pull(node);
}

int charToint(char c) {
  if (c == 'J')
    return 0;
  if (c == 'O')
    return 1;
  return 2;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  pows[0] = pair(1, 1);
  for (int i = 1; i < MAXN; ++i)
    pows[i] = mult(pows[i - 1], pair(BASE, BASE));

  int N;
  cin >> N;
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;

  build(1, 0, N - 1);
  set<H> goodHash;

  for (int n1 = 0; n1 < 3; ++n1)
    for (int n2 = 0; n2 < 3; ++n2)
      for (int n3 = 0; n3 < 3; ++n3)
        if ((n1 + n2 + n3) % 3 == 1) {
          H h(0, 0);
          for (int i = 0; i < N; ++i) {
            int x = (n1 * charToint(s1[i]) + n2 * charToint(s2[i]) +
                     n3 * charToint(s3[i])) %
                    3;
            h = add(h, mult(pair(x, x), pows[i]));
          }
          goodHash.insert(h);
        }

  int Q;
  cin >> Q;
  string T0;
  cin >> T0;
  for (int i = 0; i < N; ++i)
    rangeSet(1, i, i, charToint(T0[i]));

  cout << (goodHash.count(rangeHash[1]) ? "Yes" : "No") << '\n';

  for (int i = 0; i < Q; ++i) {
    int L, R;
    char c;
    cin >> L >> R >> c;
    rangeSet(1, L - 1, R - 1, charToint(c));
    cout << (goodHash.count(rangeHash[1]) ? "Yes" : "No") << '\n';
  }
}

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