結果
問題 | No.875 Range Mindex Query |
ユーザー | simamumu |
提出日時 | 2019-09-06 22:09:14 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,890 bytes |
コンパイル時間 | 186 ms |
コンパイル使用メモリ | 11,044 KB |
実行使用メモリ | 57,864 KB |
最終ジャッジ日時 | 2023-09-07 00:08:53 |
合計ジャッジ時間 | 5,822 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
14,640 KB |
testcase_01 | AC | 126 ms
10,636 KB |
testcase_02 | AC | 149 ms
10,484 KB |
testcase_03 | AC | 47 ms
10,228 KB |
testcase_04 | AC | 87 ms
10,372 KB |
testcase_05 | AC | 109 ms
10,660 KB |
testcase_06 | AC | 143 ms
10,712 KB |
testcase_07 | AC | 106 ms
10,500 KB |
testcase_08 | AC | 105 ms
10,692 KB |
testcase_09 | AC | 81 ms
10,428 KB |
testcase_10 | AC | 179 ms
10,820 KB |
testcase_11 | TLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
ソースコード
from collections import defaultdict,deque import sys,heapq,bisect,math,itertools,string,queue,copy,time sys.setrecursionlimit(10**8) INF = float('inf') mod = 10**9+7 eps = 10**-7 def inp(): return int(sys.stdin.readline()) def inpl(): return list(map(int, sys.stdin.readline().split())) def inpl_str(): return list(sys.stdin.readline().split()) class Node: def __init__(self,value,index): self.value = value self.index = index def items(self): return [self.value,self.index] class SegmentTree: def __init__(self,N,d): self.N0 = 2**(N-1).bit_length() self.nodes = [Node(d,i+1-self.N0) for i in range(2*self.N0)] def update(self,i,x): #iの値をxに更新 i += self.N0 - 1 self.nodes[i].value = x while i > 0: i = (i-1)//2 self.nodes[i] = copy.deepcopy(self.process(self.nodes[i*2+1],self.nodes[i*2+2])) def query(self,L,R): #[L,R)の値 ans = Node(INF,INF) L += self.N0 R += self.N0 while L < R: if R&1 : R -= 1 ans = copy.deepcopy(self.process(ans,self.nodes[R-1])) if L&1 : ans = copy.deepcopy(self.process(ans,self.nodes[L-1])) L += 1 L >>= 1; R >>= 1 return ans def process(self,node_x,node_y): #x,yが子の時,親に返る値 if node_x.value < node_y.value: return node_x else: return node_y N,Q = inpl() aa = inpl() ST = SegmentTree(N+1,INF) for i,a in enumerate(aa): ST.update(i,a) for _ in range(Q): #print([node.items() for node in ST.nodes]) q,L,R = inpl() L,R = L-1, R-1 if q == 1: l = ST.nodes[L+ST.N0-1].value r = ST.nodes[R+ST.N0-1].value ST.update(L,r) ST.update(R,l) else: print(ST.query(L,R+1).index+1)