結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
|
提出日時 | 2025-07-14 13:47:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 545 ms / 3,000 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 328 ms |
コンパイル使用メモリ | 82,640 KB |
実行使用メモリ | 85,684 KB |
最終ジャッジ日時 | 2025-07-14 13:47:39 |
合計ジャッジ時間 | 12,909 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
class SegTree: def __init__(self, arr, op, e): self._n = len(arr) self._op = op self._e = e self._size = 1 << (self._n - 1).bit_length() self._tree = [self._e] * (2 * self._size) for i in range(self._n): self[i] = arr[i] def get(self, k): assert 0 <= k < self._n return self._tree[k + self._size] def set(self, k, x): assert 0 <= k < self._n k += self._size self._tree[k] = x while k > 1: k >>= 1 self._tree[k] = self._op(self._tree[k << 1], self._tree[k << 1 ^ 1]) def all_prod(self): return self._tree[1] def prod(self, l, r): assert 0 <= l <= r <= self._n res_l = res_r = self._e l += self._size r += self._size while l < r: if l & 1: res_l = self._op(res_l, self._tree[l]) l += 1 if r & 1: r -= 1 res_r = self._op(self._tree[r], res_r) l >>= 1 r >>= 1 return self._op(res_l, res_r) def max_right(self, l, f): ''' f(op(a[l], a[l + 1], ..., a[r - 1])) = True となる最大の r ''' # assert 0 <= l <= self._n if not 0 <= l <= self._n: return self._n assert f(self._e) if l == self._n: return self._n l += self._size res = self._e first = True while first or (l & -l) != l: first = False while l % 2 == 0: l >>= 1 if not f(self._op(res, self._tree[l])): while l < self._size: l *= 2 if f(self._op(res, self._tree[l])): res = self._op(res, self._tree[l]) l += 1 return l - self._size res = self._op(res, self._tree[l]) l += 1 return self._n def min_left(self, r, f): ''' f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l ''' # assert 0 <= r <= self._n if not 0 <= r <= self._n: return 0 assert f(self._e) if r == 0: return 0 r += self._size res = self._e first = True while first or (r & -r) != r: first = False r -= 1 while r > 1 and r % 2: r >>= 1 if not f(self._op(self._tree[r], res)): while r < self._size: r = 2 * r + 1 if f(self._op(self._tree[r], res)): res = self._op(self._tree[r], res) r -= 1 return r + 1 - self._size res = self._op(self._tree[r], res) return 0 def chmin(self, k, x): self[k] = min(self[k], x) def chmax(self, k, x): self[k] = max(self[k], x) def __getitem__(self, k): return self.get(k) def __setitem__(self, k, x): self.set(k, x) def __iter__(self): for i in range(self._n): yield self[i] def __str__(self): return str(list(self)) Q = int(input()) seg = SegTree([0] * (Q + 1), max, 0) last = 0 for _ in range(Q): t, x = map(int, input().split()) if t == 1: seg[last] = x last += 1 else: res = seg.prod(last - x, last) print(res)