Submission #737688

#	Time	Username	Problem	Language	Result	Execution time	Memory
737688		veehz	Crossing (JOI21_crossing)	C++17	49 / 100	7057 ms	27992 KiB

Main

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

typedef long long ll;
typedef long double ld;
#define pb push_back

/* Segment Tree */
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
  /* S op(S a, S b) {} -> Combine values */
  /* S e() {} -> Initial value (0) */
  int _n;
  vector<S> d;
  segtree() : segtree(0) {}
  explicit segtree(int n) : segtree(vector<S>(n, e())) {}
  explicit segtree(vector<S> v) : _n(int(v.size())) {
    d.assign(4 * _n, e());
    if (_n) build(v);
  }
  void build(vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      d[v] = op(d[v * 2], d[v * 2 + 1]);
    }
  }
  void set(int pos, S new_val, int tl = 0, int tr = -1, int v = 1) {
    assert(0 <= pos && pos < _n);
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        set(pos, new_val, tl, tm, v * 2);
      else
        set(pos, new_val, tm + 1, tr, v * 2 + 1);
      d[v] = op(d[2 * v], d[2 * v + 1]);
    }
  }
  S prod(int l, int r, int tl = 0, int tr = -1, int v = 1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return e();
    if (l == tl && r == tr) return d[v];
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), tl, tm, 2 * v),
              prod(max(l, tm + 1), r, tm + 1, tr, 2 * v + 1));
  }
  // new - might have bugs
  size_t prod_lower_bound(S x, int tl = 0, int tr = -1, int v = 1,
                          S acc = e()) {
    if (tr == -1) {
      if (prod(0, _n - 1) < x) return _n;
      tr = _n - 1;
    }
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (op(acc, d[2 * v]) < x)
      return prod_lower_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v]));
    else
      return prod_lower_bound(x, tl, tm, 2 * v, acc);
  }
  size_t prod_upper_bound(S x, int tl = 0, int tr = -1, int v = 1,
                          S acc = e()) {
    if (tr == -1) {
      if (prod(0, _n - 1) <= x) return _n;
      tr = _n - 1;
    }
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (op(acc, d[2 * v]) <= x)
      return prod_upper_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v]));
    else
      return prod_upper_bound(x, tl, tm, 2 * v, acc);
  }
};
/* End: Segment Tree */

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct lazySegtree {
  int _n;
  vector<S> d;
  vector<F> lz;
  lazySegtree() : lazySegtree(0) {}
  lazySegtree(int n) : lazySegtree(vector<S>(n, e())) {}
  lazySegtree(vector<S> a)
      : _n((int)a.size()), d(4 * (int)a.size()), lz(4 * (int)a.size(), id()) {
    build(a);
  }

  void build(const vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, 2 * v, tl, tm);
      build(a, 2 * v + 1, tm + 1, tr);
      d[v] = op(d[2 * v], d[2 * v + 1]);
    }
  }

  void apply(int v, F f) {
    d[v] = mapping(f, d[v]);
    lz[v] = composition(f, lz[v]);
  }

  void push(int v) {
    apply(2 * v, lz[v]);
    apply(2 * v + 1, lz[v]);
    lz[v] = id();
  }

  void update(int v) { d[v] = op(d[2 * v], d[2 * v + 1]); }

  void set(int pos, S val, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;

    if (tl == tr) {
      d[v] = val;
    } else {
      int tm = (tl + tr) / 2;
      push(v);
      if (pos <= tm) {
        set(pos, val, 2 * v, tl, tm);
      } else {
        set(pos, val, 2 * v + 1, tm + 1, tr);
      }
      update(v);
    }
  }

  /** Apply to [l,r] */
  void apply(int l, int r, F f, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return;

    if (l == tl && r == tr) {
      apply(v, f);
    } else {
      push(v);
      int tm = (tl + tr) / 2;
      apply(l, min(r, tm), f, 2 * v, tl, tm);
      apply(max(l, tm + 1), r, f, 2 * v + 1, tm + 1, tr);
      update(v);
    }
  }

  /** a[l] x a[l+1] x ... x a[r] */
  S prod(int l, int r, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return e();

    if (l == tl && r == tr) return d[v];

    push(v);
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), 2 * v, tl, tm),
              prod(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr));
  }
};

// for comparing sa (= sb = sc)
typedef char sk;

sk skop(sk a, sk b) {
  if (b == ' ') return a;
  if (a == ' ') return b;
  if (a == 'X' || b == 'X' || a != b) return 'X';
  return a;
}
sk ske() { return ' '; }

inline segtree<sk, skop, ske> generateSegtree(string s) {
  vector<sk> skvec(s.begin(), s.end());
  return segtree<sk, skop, ske>(skvec);
}

vector<segtree<sk, skop, ske>> segtrees;

struct S {
  int val;
  int l, r;
};
S op(S a, S b) {
  int v = 0;
  for (int i = 0; i < (int)segtrees.size(); i++)
    if ((a.val & b.val) & (1 << i)) v |= (1 << i);
  return {v, min(a.l, b.l), max(a.r, b.r)};
}
S e() { return {(1 << ((int)segtrees.size())) - 1, INT_MAX, INT_MIN}; }

typedef char F;
// 0 = none
// 1 = J, 2 = O, 3 = I
S mapping(F f, S x) {
  if (f == ' ') return x;
  int v = 0;
  for (int i = 0; i < (int)segtrees.size(); i++) {
    if (f == segtrees[i].prod(x.l, x.r)) v |= (1 << i);
  }
  return {v, x.l, x.r};
}

F composition(F f, F g) { return f == ' ' ? g : f; }

F id() { return ' '; }

string cross(string a, string b) {
  string c;
  for (int i = 0; i < (int)a.size(); i++) {
    if (a[i] == b[i])
      c.pb(a[i]);
    else if (a[i] == 'J' && b[i] == 'O')
      c.pb('I');
    else if (a[i] == 'J' && b[i] == 'I')
      c.pb('O');
    else if (a[i] == 'O' && b[i] == 'J')
      c.pb('I');
    else if (a[i] == 'O' && b[i] == 'I')
      c.pb('J');
    else if (a[i] == 'I' && b[i] == 'J')
      c.pb('O');
    else if (a[i] == 'I' && b[i] == 'O')
      c.pb('J');
  }
  return c;
}

int main() {
  int n;
  cin >> n;

  set<string> s;
  for (int i = 0; i < 3; i++) {
    string t;
    cin >> t;
    s.insert(t);
  }

  while (true) {
    vector<string> v;
    for (auto& t : s) v.pb(t);
    bool hasNew = false;
    for (int i = 0; i < (int)v.size(); i++) {
      for (int j = i + 1; j < (int)v.size(); j++) {
        string t = cross(v[i], v[j]);
        if (s.find(t) == s.end()) {
          s.insert(t);
          hasNew = true;
        }
      }
    }
    if (!hasNew) break;
  }
  vector<string> v;
  for (auto& t : s) v.pb(t);
  for (auto& t : v) segtrees.pb(generateSegtree(t));

  int q;
  cin >> q;
  string t;
  cin >> t;
  vector<S> svec(n);
  for (int i = 0; i < n; i++) {
    int tmp = 0;
    for (int j = 0; j < (int)v.size(); j++) {
      if (v[j][i] == t[i]) tmp |= (1 << j);
    }
    svec[i] = {tmp, i, i};
  }

  lazySegtree<S, op, e, F, mapping, composition, id> seg(svec);

  cout << (seg.prod(0, n - 1).val ? "Yes" : "No") << endl;
  while (q--) {
    int l, r;
    char c;
    cin >> l >> r >> c;

    seg.apply(l - 1, r - 1, c);
    cout << (seg.prod(0, n - 1).val ? "Yes" : "No") << endl;
  }
}

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