結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー | navel_tos |
提出日時 | 2023-05-20 01:57:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 407 ms / 2,000 ms |
コード長 | 2,421 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 138,724 KB |
最終ジャッジ日時 | 2024-06-01 02:18:26 |
合計ジャッジ時間 | 16,482 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
52,900 KB |
testcase_01 | AC | 358 ms
107,352 KB |
testcase_02 | AC | 382 ms
126,604 KB |
testcase_03 | AC | 349 ms
117,180 KB |
testcase_04 | AC | 344 ms
126,132 KB |
testcase_05 | AC | 391 ms
118,564 KB |
testcase_06 | AC | 366 ms
126,008 KB |
testcase_07 | AC | 402 ms
138,724 KB |
testcase_08 | AC | 407 ms
127,120 KB |
testcase_09 | AC | 385 ms
126,672 KB |
testcase_10 | AC | 371 ms
104,032 KB |
testcase_11 | AC | 396 ms
123,424 KB |
testcase_12 | AC | 398 ms
123,296 KB |
testcase_13 | AC | 393 ms
123,372 KB |
testcase_14 | AC | 390 ms
114,140 KB |
testcase_15 | AC | 389 ms
123,916 KB |
testcase_16 | AC | 391 ms
124,032 KB |
testcase_17 | AC | 396 ms
126,668 KB |
testcase_18 | AC | 397 ms
126,520 KB |
testcase_19 | AC | 394 ms
123,500 KB |
testcase_20 | AC | 388 ms
114,176 KB |
testcase_21 | AC | 393 ms
136,324 KB |
testcase_22 | AC | 395 ms
136,296 KB |
testcase_23 | AC | 393 ms
136,296 KB |
testcase_24 | AC | 406 ms
136,508 KB |
testcase_25 | AC | 386 ms
136,392 KB |
testcase_26 | AC | 393 ms
134,608 KB |
testcase_27 | AC | 403 ms
136,172 KB |
testcase_28 | AC | 398 ms
136,192 KB |
testcase_29 | AC | 397 ms
136,424 KB |
testcase_30 | AC | 396 ms
136,140 KB |
testcase_31 | AC | 254 ms
132,820 KB |
testcase_32 | AC | 260 ms
132,800 KB |
testcase_33 | AC | 256 ms
133,820 KB |
testcase_34 | AC | 281 ms
134,008 KB |
testcase_35 | AC | 279 ms
135,372 KB |
testcase_36 | AC | 278 ms
134,312 KB |
testcase_37 | AC | 288 ms
79,240 KB |
testcase_38 | AC | 401 ms
126,288 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[Lt])