Submission #1037110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037110		juicy	Crossing (JOI21_crossing)	C++17	26 / 100	240 ms	19500 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

bool prime(int N) {
  for (int i = 2; i * i <= N; ++i) {
    if (N % i == 0) {
      return 0;
    }
  }
  return 1;
}

int rand_mod() {
  int x = rand(1e9, 2e9);
  while (!prime(x)) {
    --x;
  }
  return x;
}

int rand_base() {
  int x = rand(13, 999999);
  while (!prime(x)) {
    --x;
  }
  return x;
}

int n, q;
array<int, 3> MD{rand_mod(), rand_mod(), rand_mod()}, base{rand_base(), rand_base(), rand_base()};
array<int, 3> pw[N], pf[N], sum[N], s[4 * N];
int lz[4 * N];
map<array<int, 3>, bool> mp;
string S;

int add(int x, int y, int c) {
  return ((long long) x + y) % MD[c];
}

int conv(char c) {
  return c == 'J' ? 1 : (c == 'O' ? 2 : 3);
}

void pull(int id, int l, int r) {
  int md = (l + r) / 2; 
  for (int i = 0; i < 3; ++i) {
    s[id][i] = add((long long) s[id * 2][i] * pw[r - md][i] % MD[i], s[id * 2 + 1][i], i);
  }
}

void bld(int id = 1, int l = 1, int r = n) {
  for (int i = 0; i < 3; ++i) {
    sum[id][i] = pf[r - l][i];
  }
  if (l == r) {
    int x = conv(S[l - 1]);
    s[id] = {x, x, x};
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  pull(id, l, r);
}

void app(int id, int x) {
  for (int i = 0; i < 3; ++i) {
    s[id][i] = (long long) sum[id][i] * x % MD[i];
  }
  lz[id] = x;
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (u <= md) {
    upd(u, v, x, id * 2, l, md);
  } 
  if (md < v) {
    upd(u, v, x, id * 2 + 1, md + 1, r);
  }
  pull(id, l, r);
}

string cross(const string &a, const string &b) {
  string res;
  for (int i = 0; i < n; ++i) {
    if (a[i] == b[i]) {
      res += a[i];
    } else {
      for (auto c : {'J', 'O', 'I'}) {
        if (c != a[i] && c != b[i]) {
          res += c;
        }
      }
    }
  }
  return res;
}

array<int, 3> get(const string &s) {
  array<int, 3> h{}; 
  for (char c : s) {
    for (int i = 0; i < 3; ++i) {
      h[i] = add((long long) h[i] * base[i] % MD[i], conv(c), i); 
    }
  }
  return h;
}

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

  cin >> n;
  vector<string> st;
  for (int i = 0; i < 3; ++i) {
    string s; cin >> s;
    st.push_back(s);
    mp[get(s)] = 1;
  }  
  for (int i = 0; i < 3; ++i) {
    for (int j = i + 1; j < 3; ++j) {
      auto mix = cross(st[i], st[j]);
      auto h = get(mix);
      if (!mp.count(h)) {
        mp[h] = 1;
        st.push_back(mix);
      }
    }
  }
  bool flg = 1;
  while (flg) {
    flg = 0;
    for (int i = 0; i + 1 < st.size(); ++i) {
      auto mix = cross(st[i], st.back());
      auto h = get(mix);
      if (!mp.count(h)) {
        st.push_back(mix);
        mp[h] = 1;
        flg = 1;
        break;
      }
    }
  }
  for (auto it : {0, 1, 2}) {
    pw[0][it] = pf[0][it] = 1;
    for (int i = 1; i <= n; ++i) {
      pw[i][it] = (long long) pw[i - 1][it] * base[it] % MD[it];
      pf[i][it] = add(pf[i - 1][it], pw[i][it], it);
    }
  }
  cin >> q >> S;
  bld();
  auto qry = [&]() {
    cout << (mp.count(s[1]) ? "Yes" : "No") << "\n";
  };
  qry();
  while (q--) {
    int l, r; char c; cin >> l >> r >> c;
    upd(l, r, conv(c));
    qry();
  }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i + 1 < st.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~

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