結果
問題 | No.875 Range Mindex Query |
ユーザー | DrDrpilot |
提出日時 | 2022-06-21 17:10:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 649 ms / 2,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 92,288 KB |
最終ジャッジ日時 | 2024-04-22 11:45:34 |
合計ジャッジ時間 | 6,965 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
52,352 KB |
testcase_01 | AC | 82 ms
70,864 KB |
testcase_02 | AC | 102 ms
75,648 KB |
testcase_03 | AC | 48 ms
60,416 KB |
testcase_04 | AC | 61 ms
65,664 KB |
testcase_05 | AC | 49 ms
59,776 KB |
testcase_06 | AC | 79 ms
69,760 KB |
testcase_07 | AC | 90 ms
73,472 KB |
testcase_08 | AC | 69 ms
65,792 KB |
testcase_09 | AC | 62 ms
66,048 KB |
testcase_10 | AC | 98 ms
75,264 KB |
testcase_11 | AC | 649 ms
88,448 KB |
testcase_12 | AC | 605 ms
84,900 KB |
testcase_13 | AC | 567 ms
92,288 KB |
testcase_14 | AC | 562 ms
90,676 KB |
testcase_15 | AC | 630 ms
92,288 KB |
testcase_16 | AC | 535 ms
91,904 KB |
testcase_17 | AC | 570 ms
92,160 KB |
testcase_18 | AC | 543 ms
92,032 KB |
ソースコード
def segfunc(x,y): return min(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())) lis=[0]*(n+1) for i in range(n): lis[a[i]]=i seg=SegTree(a,10**18,segfunc) for _ in range(q): com,x,y=map(int,input().split()) x-=1;y-=1 if com==2: num=seg.query(x,y) #print(num) print(lis[num]+1) else: num_x=seg.select(x);num_y=seg.select(y) #print(num_x,num_y) point_num_x=lis[num_x];point_num_y=lis[num_y] lis[num_x]=point_num_y lis[num_y]=point_num_x seg.update(x,num_y) seg.update(y,num_x)