Submission #737684

#TimeUsernameProblemLanguageResultExecution timeMemory
737684veehzCrossing (JOI21_crossing)C++17
49 / 100
7022 ms84844 KiB
#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 { 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 char F; // 0 = none // 1 = J, 2 = O, 3 = I S mapping(F f, S x) { if (f == ' ') return x; vector<bool> v(segtrees.size()); for (int i = 0; i < (int)segtrees.size(); i++) { v[i] = (f == segtrees[i].prod(x.l, x.r)); } 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++) { 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; seg.apply(l - 1, r - 1, c); cout << (seg.prod(0, n - 1).compress() ? "Yes" : "No") << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...