結果

問題 No.2308 [Cherry 5th Tune B] もしかして、真?
ユーザー DaylightDaylight
提出日時 2023-05-19 21:57:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 11,626 bytes
コンパイル時間 2,952 ms
コンパイル使用メモリ 225,060 KB
実行使用メモリ 48,368 KB
最終ジャッジ日時 2024-05-10 05:30:40
合計ジャッジ時間 76,903 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1,732 ms
18,404 KB
testcase_02 TLE -
testcase_03 AC 1,899 ms
26,240 KB
testcase_04 AC 1,883 ms
29,740 KB
testcase_05 AC 1,946 ms
29,552 KB
testcase_06 TLE -
testcase_07 AC 1,988 ms
34,924 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 1,920 ms
26,632 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 AC 862 ms
48,360 KB
testcase_32 AC 877 ms
48,360 KB
testcase_33 AC 864 ms
48,360 KB
testcase_34 AC 1,029 ms
48,360 KB
testcase_35 AC 995 ms
48,232 KB
testcase_36 AC 1,059 ms
48,324 KB
testcase_37 AC 72 ms
5,376 KB
testcase_38 TLE -
権限があれば一括ダウンロードができます

ソースコード

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;
}
void solve() {
	int N;
	cin >> N;
	vector<string> X(N);
	vector<string> Y(N - 1);
	cin >> X >> Y;
	vi SS(N - 1);
	cin >> SS;
	Treap<S, op, e, F, mapping, composition, id> treap;
	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;
	}
}
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}
0