結果
問題 | No.875 Range Mindex Query |
ユーザー | Shuji Yamaguchi |
提出日時 | 2021-06-15 16:35:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 457 ms / 2,000 ms |
コード長 | 3,285 bytes |
コンパイル時間 | 1,081 ms |
コンパイル使用メモリ | 87,232 KB |
実行使用メモリ | 111,780 KB |
最終ジャッジ日時 | 2023-08-27 07:32:17 |
合計ジャッジ時間 | 6,999 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
71,644 KB |
testcase_01 | AC | 127 ms
77,660 KB |
testcase_02 | AC | 128 ms
77,196 KB |
testcase_03 | AC | 99 ms
76,756 KB |
testcase_04 | AC | 109 ms
76,972 KB |
testcase_05 | AC | 97 ms
76,844 KB |
testcase_06 | AC | 114 ms
77,464 KB |
testcase_07 | AC | 116 ms
77,560 KB |
testcase_08 | AC | 103 ms
77,332 KB |
testcase_09 | AC | 106 ms
77,356 KB |
testcase_10 | AC | 121 ms
77,328 KB |
testcase_11 | AC | 457 ms
105,512 KB |
testcase_12 | AC | 416 ms
98,856 KB |
testcase_13 | AC | 397 ms
111,780 KB |
testcase_14 | AC | 390 ms
108,672 KB |
testcase_15 | AC | 431 ms
111,756 KB |
testcase_16 | AC | 392 ms
111,428 KB |
testcase_17 | AC | 412 ms
111,704 KB |
testcase_18 | AC | 416 ms
111,736 KB |
ソースコード
from collections import defaultdict as dd 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]) def __str__(self): return str([self.get(i) for i in range(self.n)]) N, Q = map(int, input().split()) A = list(map(int, input().split())) G = segtree(A, min, float('inf')) d = dd() for i, a in enumerate(A): d[a] = i query = [] for i in range(Q): k, l, r = map(int, input().split()) query.append((k, l, r)) for k, l, r in query: if k == 1: lv = G.get(l-1) rv = G.get(r-1) G.set(l-1, rv) G.set(r-1, lv) d[lv] = r-1 d[rv] = l-1 else: # k == 2 v = G.prod(l-1, r) print(d[v]+1)