結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
|
提出日時 | 2025-07-11 21:39:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 396 ms / 3,000 ms |
コード長 | 3,116 bytes |
コンパイル時間 | 427 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 103,992 KB |
最終ジャッジ日時 | 2025-07-12 10:53:00 |
合計ジャッジ時間 | 8,179 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
class SegTree: def __init__(self, op, e, n, v=None): self._n = n self._op = op self._e = e self._log = (n - 1).bit_length() self._size = 1 << self._log self._d = [self._e()] * (self._size << 1) if v is not None: for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._d[i] = self._op(self._d[i << 1], self._d[i << 1 | 1]) def set(self, p, x): p += self._size self._d[p] = x while p: l, r = p, p^1 if l > r: l, r = r, l self._d[p >> 1] = self._op(self._d[l], self._d[r]) p >>= 1 def get(self, p): return self._d[p + self._size] #[l, r)の区間で求める def prod(self, l, r): sml, smr = self._e(), 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: r -= 1 smr = self._op(self._d[r], smr) 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 <= self._n assert f(self._e()) if l == self._n: return self._n l += self._size # 葉に移動 sm = self._e() # 確定した区間の積を保持する変数 while True: while l % 2 == 0: l >>= 1 # 右ノードになるまで if not f(self._op(sm, self._d[l])): # STEP2 while l < self._size: l <<= 1 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 # f(prod(l, N))=Trueが確定 return self._n def min_left(self, r, f): assert 0 <= r <= self._n assert f(self._e()) if r == 0: return 0 r += self._size sm = self._e() while True: r -= 1 while r > 1 and r % 2: r >>= 1 # 左子ノードになるまで if not f(self._op(self._d[r], sm)): # STEP2 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 op(x, y): return max(x, y) def e(): return 0 import sys input = sys.stdin.readline Q = int(input()) query = [list(map(int, input().split())) for _ in range(Q)] ST = SegTree(op, e, Q) idx = 0 for t, v in query: if t==1: ST.set(idx, v) idx += 1 else: ans = ST.prod(idx-v, idx) print(ans)