結果
問題 | No.1091 Range Xor Query |
ユーザー | DrDrpilot |
提出日時 | 2022-04-13 14:38:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 677 ms / 2,000 ms |
コード長 | 1,359 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 87,280 KB |
実行使用メモリ | 111,568 KB |
最終ジャッジ日時 | 2023-08-25 00:54:05 |
合計ジャッジ時間 | 17,778 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
71,340 KB |
testcase_01 | AC | 66 ms
71,488 KB |
testcase_02 | AC | 65 ms
71,244 KB |
testcase_03 | AC | 193 ms
96,748 KB |
testcase_04 | AC | 446 ms
81,020 KB |
testcase_05 | AC | 462 ms
110,940 KB |
testcase_06 | AC | 103 ms
80,660 KB |
testcase_07 | AC | 493 ms
92,852 KB |
testcase_08 | AC | 633 ms
96,884 KB |
testcase_09 | AC | 376 ms
82,864 KB |
testcase_10 | AC | 460 ms
102,116 KB |
testcase_11 | AC | 576 ms
107,452 KB |
testcase_12 | AC | 374 ms
107,920 KB |
testcase_13 | AC | 677 ms
94,812 KB |
testcase_14 | AC | 503 ms
101,720 KB |
testcase_15 | AC | 526 ms
107,820 KB |
testcase_16 | AC | 527 ms
83,524 KB |
testcase_17 | AC | 650 ms
104,692 KB |
testcase_18 | AC | 218 ms
79,364 KB |
testcase_19 | AC | 224 ms
94,876 KB |
testcase_20 | AC | 639 ms
94,344 KB |
testcase_21 | AC | 376 ms
79,292 KB |
testcase_22 | AC | 610 ms
104,464 KB |
testcase_23 | AC | 570 ms
111,492 KB |
testcase_24 | AC | 594 ms
111,500 KB |
testcase_25 | AC | 573 ms
111,568 KB |
testcase_26 | AC | 569 ms
111,420 KB |
testcase_27 | AC | 598 ms
111,476 KB |
ソースコード
def segfunc(x,y): return x^y class SegTree: def __init__(self,x_list,init,segfunc): self.init=init self.segfunc=segfunc self.Height=len(x_list).bit_length()+1 self.Tree=[init]*(2**self.Height) self.num=2**(self.Height-1) for i in range(len(x_list)): self.Tree[2**(self.Height-1)+i]=x_list[i] for i in range(2**(self.Height-1)-1,0,-1): self.Tree[i]=segfunc(self.Tree[2*i],self.Tree[2*i+1]) def select(self,k): return self.Tree[k+self.num] def update(self,k,x): i=k+self.num self.Tree[i]=x while i>1: if i%2==0: self.Tree[i//2]=self.segfunc(self.Tree[i],self.Tree[i+1]) else: self.Tree[i//2]=self.segfunc(self.Tree[i-1],self.Tree[i]) i//=2 def query(self,l,r): result=self.init l+=self.num r+=self.num+1 while l<r: if l%2==1: result=self.segfunc(result,self.Tree[l]) l+=1 if r%2==1: result=self.segfunc(result,self.Tree[r-1]) l//=2 r//=2 return result n,q=map(int,input().split()) a=list(map(int,input().split())) seg=SegTree(a,0,segfunc) for _ in range(q): l,r=map(int,input().split()) print(seg.query(l-1,r-1))