結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
👑 ![]() |
提出日時 | 2023-04-24 10:39:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 7,199 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 145,100 KB |
最終ジャッジ日時 | 2024-12-18 01:56:09 |
合計ジャッジ時間 | 21,475 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
class Fenwick_Tree:def __init__(self, N, A=None):self.N=Nif A==None:self.data=[0]*Nelse:assert len(A)==Nself.data=Aself.__build()def __build(self):data=self.datafor i in range(1, self.N+1):if i+(i&(-i))<=self.N:data[i+(i&(-i))-1]+=data[i-1]def add(self, i, x):i+=1data=self.datawhile i<=self.N:data[i-1]+=xi+=i&(-i)def sum(self, i):S=0data=self.datawhile i:S+=data[i-1]i-=i&(-i)return Sdef range_sum(self,l,r):return self.sum(r)-self.sum(l)def bisect_left(self, x, default=-1):i=0k=1<<self.N.bit_length()data=self.datawhile k:if i+k<=self.N and data[i+k-1]<x:x-=self.data[i+k-1]i+=kk>>=1return i if x else defaultdef bisect_right(self, x, default=-1):i=0k=1<<self.N.bit_length()data=self.datawhile k:if i+k<=self.N and data[i+k-1]<=x:x-=self.data[i+k-1]i+=kk>>=1return i if i<self.N else defaultclass Ordered_Set:def __init__(self, N, multiple=False, S=None):self.N=Nself.multiple=bool(multiple)if (not multiple) and S:S=[1 if S[i] else 0 for i in range(N)]self.Fenwick=Fenwick_Tree(N,S)self.__card=self.Fenwick.sum(N)def __contains__(self, x):return bool(self.count(x))def count(self, x):return self.Fenwick.range_sum(x,x+1)def __len__(self):return self.__carddef __bool__(self):return bool(len(self))def add(self, x, k=1):""" x を k 個 (多重集合のとき) 加える."""if (not self.multiple) and (x in self):returnif not self.multiple:k=1self.Fenwick.add(x,k)self.__card+=kdef discard(self, x, k=1):""" x を k 個 (多重集合のとき) 削除する.x: intk: k=-1 とすると, x を全て削除する."""if x not in self:returnif k==-1:k=self.count(x)elif not self.multiple:k=1self.Fenwick.add(x,-k)self.__card-=kdef remove(self, x):""" x を k 個 (多重集合のとき) 削除する.x: intk: k=-1 とすると, x を全て削除する."""if x not in self:raise KeyError(x)if k==-1:k=self.count(x)elif not self.multiple:k=1self.Fenwick.add(x, -k)self.__card-=kdef get(self, index, default=-1):size=len(self)if size<=index or size+index<0:return defaultif index<0:index+=sizereturn self.Fenwick.bisect_left(index+1)def __getitem__(self, index):size=len(self)if size<=index or size+index<0:raise IndexErrorif index<0:index+=sizereturn self.Fenwick.bisect_left(index+1)def get_min(self, default=-1):return self.get(0, default)def pop_min(self):y=self.get_min()if y==-1:raise IndexErrorself.remove(y)return ydef get_max(self, default=-1):return self.get(-1, default)def pop_max(self):y=self.get_max()if y==-1:raise IndexErrorself.remove(y)return ydef index(self, x, mode=False, default=-1):""" S[k]=x を満たす k を求める.x: intmode: False のときは k の最小値, True の時は k の最大値 (多重集合のとき有用)"""if x not in self:return defaultif mode:return self.Fenwick.sum(x+1)-1else:return self.Fenwick.sum(x)def previous(self, x, mode=True, default=-1):""" S に含まれる x 以下の要素のうち, 最大値を求める.x: intmode: False のときは "以下" が "未満" になる."""if mode:x+=1if x>=0:return self.Fenwick.bisect_left(self.Fenwick.sum(x), default)else:return defaultdef next(self, x, mode=True, default=-1):""" S に含まれる x 以上の要素のうち, 最大値を求める.x: intmode: False のときは "以上" が "より大きい" になる."""if not mode:x+=1return self.Fenwick.bisect_right(self.Fenwick.sum(x), default)def less_count(self, x, mode=False):""" x 未満の元の個数を求める.x: intmode: mode=True ならば, "未満" が "以下" になる."""if mode:x+=1return self.Fenwick.sum(x)def more_count(self, x, mode=False):""" x より大きい元の個数を求める.x: intmode: mode=True ならば, "より大きい" が "以上" になる."""return len(self)-self.less_count(x, not mode)def kth_min(self, k, default=-1):""" k 番目に小さい元を求める."""if 1<=k<=len(self):return self[k-1]else:return defaultdef kth_max(self, k, default=-1):""" k 番目に大きい元を求める."""if 1<=k<=len(self):return self[~(k-1)]else:return default#==================================================def AND(x,y):return (x and y)def OR(x,y):return (x or y)def XOR(x,y):return (x^y)def IMP(x,y):return ((not x) or y)#==================================================def solve():N=int(input())X=list(input().split())Y=[None]+list(input().split())S=list(map(int,input().split()))X=[x=="True" for x in X]U=Ordered_Set(N, S=[1]*N)left=[i-1 if i>0 else -1 for i in range(N)]right=[i+1 if i<N-1 else -1 for i in range(N)]for j in range(N-1):k=U[S[j]-1]if Y[right[k]]=="and":op=ANDelif Y[right[k]]=="or":op=ORelif Y[right[k]]=="xor":op=XORelse:op=IMPU.discard(right[k])X[k]=op(X[k], X[right[k]])X[right[k]]=Noneright[k]=right[right[k]]left[right[k]]=kreturn X[0]#==================================================import sysinput=sys.stdin.readlinewrite=sys.stdout.writeT=int(input())write("\n".join(map(str,[solve() for _ in range(T)])))