結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
|
提出日時 | 2023-05-19 21:59:56 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 11,642 bytes |
コンパイル時間 | 8,383 ms |
コンパイル使用メモリ | 277,152 KB |
最終ジャッジ日時 | 2025-02-13 01:55:04 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 TLE * 9 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define SZ(x) (int) (x).size()#define REP(i, n) for(int i = 0; i < (n); i++)#define FOR(i, a, b) for(auto i = (a); i < (b); i++)#define For(i, a, b, c) \for(auto i = (a); i != (b); i += (c))#define REPR(i, n) for(auto i = (n) -1; i >= 0; i--)#define ALL(s) (s).begin(), (s).end()#define so(V) sort(ALL(V))#define rev(V) reverse(ALL(V))#define uni(v) v.erase(unique(ALL(v)), (v).end())#define eb emplace_backtypedef unsigned long long ull;typedef long long ll;typedef vector<int> vi;typedef vector<ll> vll;typedef vector<bool> vb;typedef vector<vi> vvi;typedef vector<vll> vvll;typedef pair<int, int> PI;typedef pair<ll, ll> PL;const double EPS = 1e-6;const int MOD = 1e9 + 7;const int INF = (1 << 30);const ll LINF = 1e18;const double math_PI = acos(-1);template<typename T>vector<T> make_v(size_t a) {return vector<T>(a);}template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) {return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));}template<typename T, typename V>typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {t = v;}template<typename T, typename V>typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {for(auto& e: t) fill_v(e, v);}template<class T>bool chmax(T& a, const T& b) {if(a < b) {a = b;return true;}return false;}template<class T>bool chmin(T& a, const T& b) {if(a > b) {a = b;return true;}return false;}template<typename S, typename T>istream& operator>>(istream& is, pair<S, T>& p) {cin >> p.first >> p.second;return is;}template<typename T>istream& operator>>(istream& is, vector<T>& vec) {for(T& x: vec) is >> x;return is;}template<typename T>string join(vector<T>& vec, string splitter) {stringstream ss;REP(i, SZ(vec)) {if(i != 0) ss << splitter;ss << vec[i];}return ss.str();}template<typename T>ostream& operator<<(ostream& os, vector<T>& vec) {os << join(vec, " ");return os;}template<typename T>struct Range {private:pair<T, T> P;pair<bool, bool> bound;pair<bool, bool> inclusive;public:Range() {}Range(string l, string r, bool inl = true,bool inr = false): inclusive({ inl, inr }) {assert(l == "-");assert(r == "-");bound.first = false;bound.second = false;}Range(string l, T r, bool inl = true, bool inr = false): inclusive({ inl, inr }) {assert(l == "-");bound.first = false;bound.second = true;P.second = r;}Range(T l, string r, bool inl = true, bool inr = false): inclusive({ inl, inr }) {assert(r == "-");bound.first = true;bound.second = false;P.first = l;}Range(T l, T r, bool inl = true, bool inr = false): inclusive({ inl, inr }) {assert(l <= r);bound.first = true;bound.second = true;P.first = l;P.second = r;}pair<bool, T> getLeft() {return { bound.first, P.first };}pair<bool, T> getRight() {return { bound.second, P.second };}bool isLeftInclusive() {return inclusive.first;}bool isRightInclusive() {return inclusive.second;}};template<class S, S (*op)(S, S), S (*e)(), class F,S (*mapping)(F, S, int), F (*composition)(F, F),F (*id)()>struct Treap {private:mt19937_64 mt;uniform_int_distribution<uint64_t> rand;vector<S> value, acc;vector<F> lazy;vll priority;vi cnt;vb lazy_rev;vi lch, rch;int new_node(S v, ll p) {value.push_back(v);acc.push_back(e());lazy.push_back(id());priority.push_back(p);cnt.push_back(0);lazy_rev.push_back(false);lch.push_back(-1);rch.push_back(-1);return SZ(value) - 1;}int root = -1;int get_cnt(int t) {return t == -1 ? 0 : cnt[t];}S get_acc(int t) {return t == -1 ? e() : acc[t];}int update(int t) {if(t == -1) return t;cnt[t] = 1 + get_cnt(lch[t]) + get_cnt(rch[t]);acc[t] = op(get_acc(lch[t]),op(value[t], get_acc(rch[t])));return t;}int push(int t) {if(t == -1) return t;if(lazy_rev[t]) {lazy_rev[t] = false;swap(lch[t], rch[t]);if(lch[t] != -1)lazy_rev[lch[t]] = !lazy_rev[lch[t]];if(rch[t] != -1)lazy_rev[rch[t]] = !lazy_rev[rch[t]];}if(lazy[t] != id()) {if(lch[t] != -1) {lazy[lch[t]]= composition(lazy[t], lazy[lch[t]]);acc[lch[t]] = mapping(lazy[t], acc[lch[t]],get_cnt(lch[t]));}if(rch[t] != -1) {lazy[rch[t]]= composition(lazy[t], lazy[rch[t]]);acc[rch[t]] = mapping(lazy[t], acc[rch[t]],get_cnt(rch[t]));}value[t] = mapping(lazy[t], value[t], 1);lazy[t] = id();}return update(t);}int apply(int t, int l, int r, F f) {auto [t1, tt] = split(t, l);auto [t2, t3] = split(tt, r - l);lazy[t2] = composition(f, lazy[t2]);acc[t2] = mapping(f, acc[t2], get_cnt(t2));return merge(merge(t1, t2), t3);}int merge(int l, int r) {push(l);push(r);if(l == -1) return r;if(r == -1) return l;if(priority[l] > priority[r]) {rch[l] = merge(rch[l], r);return update(l);} else {lch[r] = merge(l, lch[r]);return update(r);}}PI split(int t, int k) {if(t == -1) return make_pair(-1, -1);push(t);int implicit_key = get_cnt(lch[t]) + 1;if(k < implicit_key) {PI s = split(lch[t], k);lch[t] = s.second;return make_pair(s.first, update(t));} else {PI s = split(rch[t], k - implicit_key);rch[t] = s.first;return make_pair(update(t), s.second);}}int insert(int t, int k, int n) {auto s = split(t, k);return merge(merge(s.first, n), s.second);}int _erase(int t, int k) {auto [tt, t3] = split(t, k + 1);auto [t1, t2] = split(tt, k);return merge(t1, t3);}int erase_range(int t, int l, int r) {auto [tt, t3] = split(t, r);auto [t1, t2] = split(tt, l);return merge(t1, t3);}pair<S, int> query(int t, int l, int r) {auto [t1, tt] = split(t, l);auto [t2, t3] = split(tt, r - l);S ret = acc[t2];return make_pair(ret, merge(merge(t1, t2), t3));}int set(int t, int k, S v) {auto [tt, t3] = split(t, k + 1);auto [t1, t2] = split(tt, k);push(t2);value[t2] = v;update(t2);return merge(merge(t1, t2), t3);}int _find(int t, S x, int offset, bool left = true) {if(op(get_acc(t), x) == x) {return -1;} else {if(left) {if(lch[t] != -1&& op(acc[lch[t]], x) != x) {return find(lch[t], x, offset, left);} else {return (op(value[t], x) != x)? offset + get_cnt(lch[t]): find(rch[t], x,offset + get_cnt(lch[t]) + 1,left);}} else {if(rch[t] != -1&& op(acc[rch[t]], x) != x) {return find(rch[t], x,offset + get_cnt(lch[t]) + 1, left);} else {return (op(value[t], x) != x)? offset + get_cnt(lch[t]): find(lch[t], x, offset, left);}}}}int reverse(int t, int l, int r) {auto [t1, tt] = split(t, l);auto [t2, t3] = split(tt, r - l);lazy_rev[t2] = !lazy_rev[t2];return merge(merge(t1, t2), t3);}int rotate(int t, int l, int m, int r) {t = reverse(t, l, r);t = reverse(t, l, l + r - m);return reverse(t, l + r - m, r);}int lower_search(int t, S x) {int ret = 0;while(t != -1) {if(x <= value[t]) {t = lch[t];} else {ret += get_cnt(lch[t]) + 1;t = rch[t];}}return ret;}int upper_search(int t, S x) {int ret = 0;while(t != -1) {if(x < value[t]) {t = lch[t];} else {ret += get_cnt(lch[t]) + 1;t = rch[t];}}return ret;}public:Treap() {mt = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());rand = uniform_int_distribution<uint64_t>(1, 1e18);}size_t size() {return size_t(get_cnt(root));}void insert(int ind, S x) {root = insert(root, ind, new_node(x, rand(mt)));}void push_back(S x) {root = insert(root, int(size()),new_node(x, rand(mt)));}void ordered_insert(S x) {int ind = lower_search(root, x);insert(ind, x);}int value_range_cnt(Range<S> range) {int L = 0;if(range.getLeft().first) {S l = range.getLeft().second;if(range.isLeftInclusive()) {L = lower_search(root, l);} else {L = upper_search(root, l);}}int R = get_cnt(root);if(range.getRight().first) {S r = range.getRight().second;if(range.isRightInclusive()) {R = upper_search(root, r);} else {R = lower_search(root, r);}}return R - L;}S value_range_sum(Range<S> range) {int L = 0;if(range.getLeft().first) {S l = range.getLeft().second;if(range.isLeftInclusive()) {L = lower_search(root, l);} else {L = upper_search(root, l);}}int R = get_cnt(root);if(range.getRight().first) {S r = range.getRight().second;if(range.isRightInclusive()) {R = upper_search(root, r);} else {R = lower_search(root, r);}}if(L == R) return e();return query(L, R);}int erase_value(S x, int cnt = -1) {int L = lower_search(root, x);int R = upper_search(root, x);if(cnt != -1) chmin(R, L + cnt);root = erase_range(root, L, R);return R - L;}int lower_search(S x) {return lower_search(root, x);}int upper_search(S x) {return upper_search(root, x);}void apply(int l, int r, F f) {root = apply(root, l, r, f);}void erase(int ind) {root = _erase(root, ind);}void erase(int l, int r) {auto [tt, t3] = split(root, r);auto [t1, t2] = split(tt, l);root = merge(t1, t3);}void reverse(int l, int r) {root = reverse(root, l, r);}void rotate(int l, int m, int r) {root = rotate(root, l, m, r);}void set(int k, S v) {root = set(root, k, v);}int find(int l, int r, S x, bool left = true) {auto [t1, tt] = split(root, l);auto [t2, t3] = split(tt, r - l);int ret = _find(t2, x, l, left);if(ret == -1) ret = r;root = merge(merge(t1, t2), t3);return ret;}S query(int l, int r) {auto [t, rt] = query(root, l, r);root = rt;return t;}S operator[](int ind) {auto [tt, t3] = split(root, ind + 1);auto [t1, t2] = split(tt, ind);S ret = acc[t2];root = merge(merge(t1, t2), t3);return ret;}};using S = ll;using F = ll;const F ID = -4e18;S op(S a, S b) {return a + b;}S e() {return 0;}S mapping(F f, S x, int sz) {if(f == ID)return x;elsereturn f;}F composition(F f, F g) {if(f == ID)return f;elsereturn g;}F id() {return ID;}Treap<S, op, e, F, mapping, composition, id> treap;void solve() {int N;cin >> N;vector<string> X(N);vector<string> Y(N - 1);cin >> X >> Y;vi SS(N - 1);cin >> SS;REP(i, N - 1) {if(X[i] == "True") {treap.push_back(1);} else {treap.push_back(0);}if(Y[i] == "and") {treap.push_back(0);} else if(Y[i] == "or") {treap.push_back(1);} else if(Y[i] == "xor") {treap.push_back(2);} else {treap.push_back(3);}}if(X[N - 1] == "True") {treap.push_back(1);} else {treap.push_back(0);}REP(i, N - 1) {int s = (SS[i] - 1) * 2;int p = treap[s];int q = treap[s + 2];int op = treap[s + 1];treap.erase(s, s + 3);int v = 0;if(op == 0) {v = p & q;} else if(op == 1) {v = p | q;} else if(op == 2) {v = p ^ q;} else {if(!p || q) {v = 1;}}treap.insert(s, v);}int v = treap[0];if(v == 1) {cout << "True" << endl;} else {cout << "False" << endl;}treap.erase(0);}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int T;cin >> T;while(T--) {solve();}return 0;}