結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー | navel_tos |
提出日時 | 2023-05-20 01:56:25 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,421 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 87,292 KB |
実行使用メモリ | 146,408 KB |
最終ジャッジ日時 | 2023-08-23 04:34:33 |
合計ジャッジ時間 | 17,506 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,324 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 | AC | 408 ms
129,472 KB |
testcase_12 | AC | 404 ms
130,160 KB |
testcase_13 | AC | 405 ms
129,304 KB |
testcase_14 | AC | 406 ms
128,348 KB |
testcase_15 | WA | - |
testcase_16 | AC | 405 ms
130,228 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 409 ms
129,440 KB |
testcase_20 | AC | 412 ms
129,136 KB |
testcase_21 | WA | - |
testcase_22 | AC | 399 ms
137,720 KB |
testcase_23 | AC | 406 ms
137,836 KB |
testcase_24 | AC | 408 ms
137,960 KB |
testcase_25 | AC | 397 ms
137,740 KB |
testcase_26 | AC | 407 ms
138,016 KB |
testcase_27 | WA | - |
testcase_28 | AC | 410 ms
137,616 KB |
testcase_29 | AC | 405 ms
137,760 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | AC | 272 ms
135,876 KB |
testcase_33 | AC | 271 ms
136,048 KB |
testcase_34 | WA | - |
testcase_35 | AC | 290 ms
137,280 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | AC | 404 ms
130,416 KB |
ソースコード
#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; ST.update(Rt,0) #演算子を使用したRt側を削除するよう変更 if Y[Rt-1]=='and': X[Lt]=oand(X[Lt],X[Rt]) elif Y[Rt-1]=='or' : X[Lt]=oor (X[Lt],X[Rt]) elif Y[Rt-1]=='xor': X[Lt]=oxor(X[Lt],X[Rt]) elif Y[Rt-1]=='imp': X[Lt]=oimp(X[Lt],X[Rt]) print(X[Rt])