結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー issaimaru
提出日時 2025-04-20 11:45:12
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,571 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 24,832 KB
最終ジャッジ日時 2025-04-20 11:45:28
合計ジャッジ時間 15,748 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 5 RE * 10 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
INF = 10**18

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [INF] * (2 * n)
    
    def update(self, idx, val):
        idx += self.n - 1
        self.tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.tree[idx] = min(self.tree[2 * idx + 1], self.tree[2 * idx + 2])
    
    def query(self, left, right):
        left += self.n - 1
        right += self.n - 1
        result = INF
        while left <= right:
            if left % 2 == 0:
                result = min(result, self.tree[left])
                left += 1
            if right % 2 == 1:
                result = min(result, self.tree[right])
                right -= 1
            left = (left - 1) // 2
            right = (right - 1) // 2
        return result

def main():
    N, Q = map(int, input().split())
    st1 = SegmentTree(N)  
    st2 = SegmentTree(N)  
    answers = []
    
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            x = query[1]
            direct = x - 1
            min1 = st1.query(1, x)
            min2 = st2.query(x, N)
            cost1 = min1 + x if min1 != INF else INF
            cost2 = min2 - x if min2 != INF else INF
            ans = min(direct, cost1, cost2)
            answers.append(ans)
        else:
            x, c = query[1], query[2]
            st1.update(x, c - x)
            st2.update(x, c + x)
    
    print('\n'.join(map(str, answers)))

if __name__ == "__main__":
    main()
0