結果

問題 No.2308 [Cherry 5th Tune B] もしかして、真?
コンテスト
ユーザー navel_tos
提出日時 2023-05-19 23:14:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,485 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 266,328 KB
最終ジャッジ日時 2024-12-20 01:45:36
合計ジャッジ時間 84,467 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 5 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder389D

'''
■考察欄
しんどそうな問題だなぁ。

T/F と 論理演算子を与える。
すげ替えを行うので、論理演算結果が最終的にどうなるか示せ。

愚直にやると、間に合わないか？

impがややこしいな。
T→T : T
T→F : F
F→T : T
F→F : T

dequeみたいなデータ構造があると楽なんだが、そんなものはない。
対決順を定められたらなぁ。

本当にやりたくないですがクエリ平方分割してやります。
区間を√N個に分割し、愚直に論理演算をやります。

区間をまたぐときが怖いから、追加ルールとして
「演算結果は左側に格納する」というものを用意しよう。

っていうか、残っている演算子の数さえわかればいいのでは？
「左からx番目の演算子はなんですか」が分かればいいなら、それはもうセグ木でいける。
'''
#Segment Tree: O(logN)
class SegmentTree:
    def __init__(self,n,identity_e,combine_f):
        self._n=n;self._size=1
        while self._size<self._n:self._size<<=1
        self._identity_e=identity_e;self._combine_f=combine_f;self._node=[self._identity_e]*2*self._size
    def build(self,array):
        assert len(array)==self._n,'array too large'
        for i,v in enumerate(array,start=self._size):self._node[i]=v
        for i in range(self._size-1,0,-1):self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def update(self,index,value):  #一点更新
        i=self._size+index;self._node[i]=value
        while i-1:i>>=1;self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def fold(self,L,R):  #区間取得: [L,R)の区間値を得る
        L+=self._size;R+=self._size;vL,vR=[self._identity_e]*2
        while L<R:
            if L&1:vL=self._combine_f(vL,self._node[L]);L+=1
            if R&1:R-=1;vR=self._combine_f(self._node[R],vR)
            L>>=1;R>>=1
        return self._combine_f(vL,vR)


from collections import defaultdict as dd
add=lambda x,y:x+y

for _ in range(int(input())):
    N=int(input()); X=list(map(lambda x: x=='True',input().split())); Y=input().split()
    S=list(map(int,input().split()))
    ST=SegmentTree(N,0,add); ST.build([1]*N)

    for i in S:  #左からi番目の真偽値と、i+1番目の真偽値を特定せよ。
        #1. 左からi番目の真偽値のインデックスを特定する
        #[0,x) の中に、まだ計算されていない真偽値がちょうどi-1個で、
        #[0,x+1) だと、真偽値がちょうどi個になる。
        #ok: 真偽値がi個未満、ng: 真偽値がi個以上 で判定しよう。
        ok,ng=0,N  #[0,x)に真偽値がいくつあるか？
        while abs(ok-ng)>1:
            mid=(ok+ng)//2; now=ST.fold(0,mid)
            (ok,ng)=(mid,ng) if now<i else (ok,mid)
        Lt=ok; ng=N
        #次に、[0,x)の中に真偽値がi+1個あるものを探す
        while abs(ok-ng)>1:
            mid=(ok+ng)//2; now=ST.fold(0,mid)
            (ok,ng)=(mid,ng) if now<i+1 else (ok,mid)
        Rt=ok
        #LtとRtの真偽値を合成し、Rt側に格納する
        ope=Y[Rt-1]
        if ope=='and': end=(X[Lt] and X[Rt])
        if ope=='or':  end=(X[Lt] or  X[Rt])
        if ope=='xor': end=(X[Lt]^X[Rt])
        if ope=='imp':
            if X[Lt]==True and X[Rt]==False: end=False
            else: end=True
        X[Rt]=end; ST.update(Lt,0)
    print(end)
0