Submission #736804

#	Time	Username	Problem	Language	Result	Execution time	Memory
736804		veehz	Crossing (JOI21_crossing)	C++17	49 / 100	7046 ms	92756 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(); }

inline segtree<sk, skop, ske> generateSegtree(string s) {
  const int n = s.size();
  vector<sk> skvec(n);
  for (int i = 0; i < n; i++) {
    skvec[i].x = {s[i] == 'J', s[i] == 'O', s[i] == 'I'};
  }
  return segtree<sk, skop, ske>(skvec);
}
vector<segtree<sk, skop, ske>> segtrees;

struct S {
  vector<bool> val;
  int l, r;
  bool compress() {
    for (int i = 0; i < (int)val.size(); i++)
      if (val[i]) return true;
    return false;
  }
};
S op(S a, S b) {
  vector<bool> v(segtrees.size());
  for (int i = 0; i < (int)segtrees.size(); i++) v[i] = (a.val[i] && b.val[i]);
  return {v, min(a.l, b.l), max(a.r, b.r)};
}
S e() { return {vector<bool>(segtrees.size(), 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--;
  vector<bool> v;
  for (int i = 0; i < (int)segtrees.size(); i++) {
    auto r = segtrees[i].prod(x.l, x.r).x;
    if (r[f] && (r[0] + r[1] + r[2] == 1))
      v.pb(true);
    else
      v.pb(false);
  }
  return {v, x.l, x.r};
}

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

F id() { return 0; }

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++) {
    vector<bool> tmp(v.size());
    for (int j = 0; j < (int)v.size(); j++){
      tmp[j] = v[j][i] == t[i];
    }
    svec[i] = {tmp, i, i};
  }

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

  cout << (seg.prod(0, n - 1).compress() ? "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).compress() ? "Yes" : "No") << endl;
  }
}

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