結果

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

ソースコード

diff # 

import sys
input = sys.stdin.readline

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [(float('inf'), float('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 + start, val - start)
            return
        mid = (start + end) // 2
        if idx <= mid:
            self.update(idx, val, node*2, start, mid)
        else:
            self.update(idx, val, node*2+1, mid+1, end)
        self.tree[node] = (min(self.tree[node*2][0], self.tree[node*2+1][0]),
                           min(self.tree[node*2][1], self.tree[node*2+1][1]))
    
    def query_min_plus(self, left, right, node=1, start=1, end=None):
        if end is None:
            end = self.n
        if left > end or right < start:
            return float('inf')
        if left <= start and end <= right:
            return self.tree[node][0]
        mid = (start + end) // 2
        return min(self.query_min_plus(left, right, node*2, start, mid),
                   self.query_min_plus(left, right, node*2+1, mid+1, end))
    
    def query_min_minus(self, left, right, node=1, start=1, end=None):
        if end is None:
            end = self.n
        if left > end or right < start:
            return float('inf')
        if left <= start and end <= right:
            return self.tree[node][1]
        mid = (start + end) // 2
        return min(self.query_min_minus(left, right, node*2, start, mid),
                   self.query_min_minus(left, right, node*2+1, mid+1, end))

def main():
    ans_list = []
    N, Q = map(int, input().split())
    seg_tree = SegmentTree(N)
    
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            x = query[1]
            min_cost = x - 1 
            if x > 1:
                min_minus = seg_tree.query_min_minus(1, x-1)
                if min_minus != float('inf'):
                    min_cost = min(min_cost, min_minus + x)
            if x <= N:  
                min_plus = seg_tree.query_min_plus(x, N)
                if min_plus != float('inf'):
                    min_cost = min(min_cost, min_plus - x)
            ans_list.append(min_cost)
        else:
            x, c = query[1], query[2]
            seg_tree.update(x, c)

    print('\n'.join(map(str, ans_list)))

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