結果

問題 No.3116 More and more teleporter
ユーザー keigo kuwata
提出日時 2025-05-23 07:26:25
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,040 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 22,648 KB
最終ジャッジ日時 2025-05-23 07:26:50
合計ジャッジ時間 23,989 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [10**18] * (2 * self.size)
    
    def update(self, pos, val):
        pos += self.size
        self.tree[pos] = min(self.tree[pos], val)
        while pos > 1:
            pos //= 2
            self.tree[pos] = min(self.tree[2*pos], self.tree[2*pos + 1])
    
    def query(self, l, r):
        # [l, r)の最小値
        l += self.size
        r += self.size
        res = 10**18
        while l < r:
            if l % 2 == 1:
                res = min(res, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = min(res, self.tree[r])
            l //= 2
            r //= 2
        return res

N, Q = map(int, input().split())

# left_seg[i] には cost - i の最小値を格納
# right_seg[i] には cost + i の最小値を格納
left_seg = SegmentTree(N + 1)
right_seg = SegmentTree(N + 1)

for _ in range(Q):
    query = list(map(int, input().split()))
    
    if query[0] == 1:
        # クエリ1: マス1からマスxへの最小コスト
        x = query[1]
        
        # 直接歩く場合
        min_cost = x - 1
        
        # x以下の位置のテレポーターを使う場合
        # min(cost - pos) + x
        left_min = left_seg.query(1, x + 1)
        if left_min < 10**18:
            min_cost = min(min_cost, left_min + x)
        
        # xより大きい位置のテレポーターを使う場合
        # min(cost + pos) - x
        right_min = right_seg.query(x + 1, N + 1)
        if right_min < 10**18:
            min_cost = min(min_cost, right_min - x)
        
        print(min_cost)
    
    else:
        # クエリ2: マスxにコストcのテレポーター設置
        x = query[1]
        c = query[2]
        
        # セグメント木を更新
        left_seg.update(x, c - x)
        right_seg.update(x, c + x)
0