結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー issaimaru
提出日時 2025-04-20 11:42:21
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,790 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 32,780 KB
最終ジャッジ日時 2025-04-20 11:42:30
合計ジャッジ時間 8,369 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [INF] * (4 * n)
    
    def update(self, idx, val, node=1, start=1, end=None):
        if end is None:
            end = self.n
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self.update(idx, val, 2 * node, start, mid)
            else:
                self.update(idx, val, 2 * node + 1, mid + 1, end)
            self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
    
    def query(self, left, right, node=1, start=1, end=None):
        if end is None:
            end = self.n
        if right < start or end < left:
            return INF
        if left <= start and end <= right:
            return self.tree[node]
        mid = (start + end) // 2
        p1 = self.query(left, right, 2 * node, start, mid)
        p2 = self.query(left, right, 2 * node + 1, mid + 1, end)
        return min(p1, p2)

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
            st1.update(x, c - x)
            st2.update(x, c + x)
    
    for ans in answers:
        print(ans)

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