結果
問題 | No.875 Range Mindex Query |
ユーザー | simamumu |
提出日時 | 2019-09-06 22:27:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 867 ms / 2,000 ms |
コード長 | 2,188 bytes |
コンパイル時間 | 284 ms |
コンパイル使用メモリ | 87,540 KB |
実行使用メモリ | 130,220 KB |
最終ジャッジ日時 | 2023-09-07 01:08:32 |
合計ジャッジ時間 | 10,976 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 187 ms
81,384 KB |
testcase_01 | AC | 218 ms
83,184 KB |
testcase_02 | AC | 218 ms
83,144 KB |
testcase_03 | AC | 196 ms
82,440 KB |
testcase_04 | AC | 205 ms
82,908 KB |
testcase_05 | AC | 204 ms
82,808 KB |
testcase_06 | AC | 220 ms
83,472 KB |
testcase_07 | AC | 215 ms
82,956 KB |
testcase_08 | AC | 209 ms
82,884 KB |
testcase_09 | AC | 208 ms
82,872 KB |
testcase_10 | AC | 227 ms
84,080 KB |
testcase_11 | AC | 817 ms
124,908 KB |
testcase_12 | AC | 680 ms
107,436 KB |
testcase_13 | AC | 767 ms
123,596 KB |
testcase_14 | AC | 771 ms
122,520 KB |
testcase_15 | AC | 867 ms
124,916 KB |
testcase_16 | AC | 795 ms
128,052 KB |
testcase_17 | AC | 814 ms
128,924 KB |
testcase_18 | AC | 825 ms
130,220 KB |
ソースコード
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,aa): self.N0 = 2**(N-1).bit_length() self.nodes = [Node(INF,i+1-self.N0) for i in range(2*self.N0-1)] for i in reversed(range(2*self.N0-1)): ind = i+1-self.N0 if ind >= N: self.nodes[i].value = INF elif N > ind >= 0: self.nodes[i].value = aa[ind] else: self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2]) 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] = self.process(self.nodes[i*2+1],self.nodes[i*2+2]) def query(self,L,R): #[L,R)の値 retnode = Node(INF,INF) L += self.N0 R += self.N0 while L < R: if R&1 : R -= 1 retnode = self.process(retnode,self.nodes[R-1]) if L&1 : retnode = self.process(retnode,self.nodes[L-1]) L += 1 L >>= 1; R >>= 1 return retnode 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,aa) ans = [] 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: ans.append(str(ST.query(L,R+1).index+1)) print('\n'.join(ans))