結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー | navel_tos |
提出日時 | 2023-05-20 01:44:29 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,370 bytes |
コンパイル時間 | 352 ms |
コンパイル使用メモリ | 87,120 KB |
実行使用メモリ | 152,756 KB |
最終ジャッジ日時 | 2023-08-23 04:28:07 |
合計ジャッジ時間 | 18,313 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,140 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 429 ms
127,264 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 430 ms
126,960 KB |
testcase_21 | AC | 433 ms
137,312 KB |
testcase_22 | WA | - |
testcase_23 | AC | 429 ms
137,240 KB |
testcase_24 | WA | - |
testcase_25 | AC | 425 ms
137,260 KB |
testcase_26 | AC | 429 ms
137,556 KB |
testcase_27 | AC | 436 ms
137,464 KB |
testcase_28 | WA | - |
testcase_29 | AC | 423 ms
137,356 KB |
testcase_30 | AC | 421 ms
137,148 KB |
testcase_31 | AC | 299 ms
135,712 KB |
testcase_32 | AC | 303 ms
135,644 KB |
testcase_33 | AC | 298 ms
135,488 KB |
testcase_34 | AC | 310 ms
136,536 KB |
testcase_35 | AC | 329 ms
136,828 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
ソースコード
#yukicoder389D もしかして、真?_AfterContest ''' 並行二分探索木が必要だよなと思っていましたが実際に必要ですね。 しかたないので実装しましょう。 でもnodeを直接覗けばいいのか。うん・・・ ''' #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) add =lambda x,y:x+y oand=lambda x,y:x&y oor =lambda x,y:x|y oxor=lambda x,y:x^y oimp=lambda x,y:y if x else True 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) #手動で平衡二分探索木 区間[0,x)がちょうどiとなる最大のiを求めよ for i in S: cntL,cntR=0,0; Lt,Rt=1,1; size=ST._size #cnt: 現在の区間より左側にある値の数 while Lt<size: if cntL+ST._node[Lt<<1|0]>=i: Lt=Lt<<1|0 else: cntL+=ST._node[Lt<<1|0]; Lt=Lt<<1|1 if cntR+ST._node[Rt<<1|0]>=i+1: Rt=Rt<<1|0 else: cntR+=ST._node[Rt<<1|0]; Rt=Rt<<1|1 Lt-=size; Rt-=size if Y[Rt-1]=='and': X[Rt]=oand(X[Lt],X[Rt]) elif Y[Rt-1]=='or' : X[Rt]=oor (X[Lt],X[Rt]) elif Y[Rt-1]=='xor': X[Rt]=oxor(X[Lt],X[Rt]) elif Y[Rt-1]=='imp': X[Rt]=oimp(X[Lt],X[Rt]) ST.update(Lt,0) print(X[Rt])