結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー i_taku
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0