This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |