Submission #1037106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037106		juicy	Crossing (JOI21_crossing)	C++17	26 / 100	119 ms	19636 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 5, base = 13;

int n, q;
long long pw[N], pf[N], sum[N], s[4 * N];
int lz[4 * N];
map<long long, bool> mp;
string S;

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

void bld(int id = 1, int l = 1, int r = n) {
  sum[id] = pf[r - l];
  if (l == r) {
    s[id] = conv(S[l - 1]);
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  s[id] = s[id * 2] * pw[r - md] + s[id * 2 + 1];
}

void app(int id, int x) {
  s[id] = sum[id] * x;
  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);
  }
  s[id] = s[id * 2] * pw[r - md] + s[id * 2 + 1];
}

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;
}

long long get(const string &s) {
  long long h = 0;
  for (char c : s) {
    h = h * base + conv(c);
  }
  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;
      }
    }
  }
  pw[0] = pf[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw[i] = pw[i - 1] * base;
    pf[i] = pf[i - 1] + pw[i];
  }
  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:111: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]
  111 |     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