Submission #736764

#	Time	Username	Problem	Language	Result	Execution time	Memory
736764		veehz	Crossing (JOI21_crossing)	C++17	26 / 100	3972 ms	23184 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)
struct sk {
  array<bool, 3> x;
  sk() : x({0, 0, 0}) {}
};

sk skop(sk a, sk b) {
  sk c;
  for (int i = 0; i < 3; i++) c.x[i] = (a.x[i] || b.x[i]);
  return c;
}
sk ske() { return sk(); }

segtree<sk, skop, ske> st;

struct S {
  bool val;
  int l, r;
};
S op(S a, S b) { return {a.val && b.val, min(a.l, b.l), max(a.r, b.r)}; }
S e() { return {true, INT_MAX, INT_MIN}; }

typedef int F;
// 0 = none
// 1 = J, 2 = O, 3 = I
S mapping(F f, S x) {
  if (f == 0) return x;
  f--;
  auto r = st.prod(x.l, x.r).x;
  if (r[f] && (r[0] + r[1] + r[2] == 1)) {
    return {true, x.l, x.r};
  }
  return {false, x.l, x.r};
}

F composition(F f, F g) {
  if (f == 0) return g;
  return f;
}

F id() { return 0; }

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

  // s[a] = s[b] = s[c]
  string s;
  cin >> s >> s >> s;
  vector<sk> skvec(n);
  for (int i = 0; i < n; i++) {
    skvec[i].x = {s[i] == 'J', s[i] == 'O', s[i] == 'I'};
  }
  st = segtree<sk, skop, ske>(skvec);

  int q;
  cin >> q;
  string t;
  cin >> t;
  vector<S> svec(n);
  for (int i = 0; i < n; i++) {
    svec[i] = {t[i] == s[i], 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;
    int f = 0;
    if (c == 'J') f = 1;
    if (c == 'O') f = 2;
    if (c == 'I') f = 3;

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

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