結果

問題 No.3116 More and more teleporter
ユーザー ponjuice
提出日時 2025-04-16 01:21:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 744 ms / 2,000 ms
コード長 1,467 bytes
コンパイル時間 449 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 87,148 KB
最終ジャッジ日時 2025-04-16 01:22:02
合計ジャッジ時間 10,221 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def op(a, b):
    return min(a, b)
def e():
    return 2*10**18

class SegmentTree:
    def __init__(self, n):
        self._n = n
        self.sz = 1
        while self.sz < n:
            self.sz <<= 1
        
        E = e()
        self.data = [E for _ in range(self.sz << 1)]

    def set(self, p, x):
        assert 0 <= p < self._n
        p += self.sz
        self.data[p] = x
        while p > 1:
            p >>= 1
            self.data[p] = op(self.data[p << 1], self.data[p << 1 | 1])
        
    def get(self, p):
        assert 0 <= p < self._n
        return self.data[p + self.sz]
    def prod(self, l, r):
        assert 0 <= l <= r <= self._n
        sl = e()
        sr = e()
        l += self.sz
        r += self.sz
        while l < r:
            if l & 1:
                sl = op(sl, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                sr = op(self.data[r], sr)
            l >>= 1
            r >>= 1
        return op(sl, sr)

n, q = map(int, input().split())
seg1 = SegmentTree(n)
seg2 = SegmentTree(n)
seg1.set(0, 0)
seg2.set(0, 0)

for _ in range(q):
    t, *args = map(int, input().split())
    if t == 1:
        x, = args
        x -= 1
        ans = min(seg1.prod(0, x) + x, seg2.prod(x, n) - x)
        print(ans)
    else:
        x, c = args
        x -= 1
        if c - x < seg1.get(x):
            seg1.set(x, c - x)
        if c + x < seg2.get(x):
            seg2.set(x, c + x)
0