結果

問題 No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー Daylight
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_back
typedef 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;
else
return f;
}
F composition(F f, F g) {
if(f == ID)
return f;
else
return 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0