結果
問題 | No.875 Range Mindex Query |
ユーザー | itsy68 |
提出日時 | 2022-06-10 04:59:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 356 ms / 2,000 ms |
コード長 | 3,326 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 81,804 KB |
実行使用メモリ | 108,244 KB |
最終ジャッジ日時 | 2023-10-21 04:35:48 |
合計ジャッジ時間 | 5,465 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge9 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
63,532 KB |
testcase_01 | AC | 71 ms
72,584 KB |
testcase_02 | AC | 80 ms
76,396 KB |
testcase_03 | AC | 56 ms
66,156 KB |
testcase_04 | AC | 65 ms
70,404 KB |
testcase_05 | AC | 55 ms
66,016 KB |
testcase_06 | AC | 68 ms
72,568 KB |
testcase_07 | AC | 78 ms
72,736 KB |
testcase_08 | AC | 65 ms
70,492 KB |
testcase_09 | AC | 63 ms
70,436 KB |
testcase_10 | AC | 81 ms
76,580 KB |
testcase_11 | AC | 356 ms
103,900 KB |
testcase_12 | AC | 302 ms
95,472 KB |
testcase_13 | AC | 315 ms
108,244 KB |
testcase_14 | AC | 307 ms
107,168 KB |
testcase_15 | AC | 354 ms
106,376 KB |
testcase_16 | AC | 293 ms
106,376 KB |
testcase_17 | AC | 311 ms
106,108 KB |
testcase_18 | AC | 318 ms
104,700 KB |
ソースコード
# import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') import sys from itertools import combinations, permutations, product, accumulate, groupby from collections import defaultdict, deque, Counter from functools import reduce from operator import add, mul import heapq import bisect import math import copy sys.setrecursionlimit(10 ** 9) input = lambda: sys.stdin.readline().rstrip() INF = float("inf") MOD = 10 ** 9 + 7 class segtree(): n=1 size=1 log=2 d=[0] op=None e=10**15 def __init__(self,V,OP,E): self.n=len(V) self.op=OP self.e=E self.log=(self.n-1).bit_length() self.size=1<<self.log self.d=[E for i in range(2*self.size)] for i in range(self.n): self.d[self.size+i]=V[i] for i in range(self.size-1,0,-1): self.update(i) def set(self,p,x): assert 0<=p and p<self.n p+=self.size self.d[p]=x for i in range(1,self.log+1): self.update(p>>i) def get(self,p): assert 0<=p and p<self.n return self.d[p+self.size] def prod(self,l,r): assert 0<=l and l<=r and r<=self.n sml=self.e smr=self.e l+=self.size r+=self.size while(l<r): if (l&1): sml=self.op(sml,self.d[l]) l+=1 if (r&1): smr=self.op(self.d[r-1],smr) r-=1 l>>=1 r>>=1 return self.op(sml,smr) def all_prod(self): return self.d[1] def max_right(self,l,f): assert 0<=l and l<=self.n assert f(self.e) if l==self.n: return self.n l+=self.size sm=self.e while(1): while(l%2==0): l>>=1 if not(f(self.op(sm,self.d[l]))): while(l<self.size): l=2*l if f(self.op(sm,self.d[l])): sm=self.op(sm,self.d[l]) l+=1 return l-self.size sm=self.op(sm,self.d[l]) l+=1 if (l&-l)==l: break return self.n def min_left(self,r,f): assert 0<=r and r<self.n assert f(self.e) if r==0: return 0 r+=self.size sm=self.e while(1): r-=1 while(r>1 & (r%2)): r>>=1 if not(f(self.op(self.d[r],sm))): while(r<self.size): r=(2*r+1) if f(self.op(self.d[r],sm)): sm=self.op(self.d[r],sm) r-=1 return r+1-self.size sm=self.op(self.d[r],sm) if (r& -r)==r: break return 0 def update(self,k): self.d[k]=self.op(self.d[2*k],self.d[2*k+1]) N, Q = map(int, input().split()) A = [0] + list(map(int, input().split())) d = dict() for i, a in enumerate(A): d[a] = i G = segtree(A, min, INF) for i in range(Q): t, l, r = map(int, input().split()) if t == 1: lv = G.get(l) rv = G.get(r) G.set(l, rv) G.set(r, lv) d[rv] = l d[lv] = r if t == 2: v = G.prod(l, r + 1) print(d[v])