結果

問題 No.3116 More and more teleporter
ユーザー Kevgen
提出日時 2025-04-18 21:28:42
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,493 ms / 2,000 ms
コード長 2,293 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 49,568 KB
最終ジャッジ日時 2025-04-18 21:29:00
合計ジャッジ時間 13,945 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, data_size, init_val):
        self.n = 1
        while self.n < data_size:
            self.n <<= 1
        self.size = self.n
        self.data = [init_val] * (2 * self.n)
        self.init_val = init_val
    
    def update(self, pos, val):
        pos += self.n - 1  # Convert to 0-based index in the array
        if self.data[pos] <= val:
            return  # No need to update if existing value is better
        self.data[pos] = val
        while pos > 1:
            pos >>= 1
            new_val = min(self.data[2 * pos], self.data[2 * pos + 1])
            if self.data[pos] == new_val:
                break
            self.data[pos] = new_val
    
    def query_min(self, l, r):
        res = self.init_val
        l += self.n - 1
        r += self.n - 1
        while l <= r:
            if l % 2 == 1:
                res = min(res, self.data[l])
                l += 1
            if r % 2 == 0:
                res = min(res, self.data[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    
    INF = 1 << 60
    min_c = [INF] * (N + 2)
    left_tree = SegmentTree(N, INF)
    right_tree = SegmentTree(N, INF)
    
    output = []
    for _ in range(Q):
        parts = input[ptr:ptr+3]
        if parts[0] == '1':
            x = int(parts[1])
            ptr += 2
            walk_cost = x - 1
            min_left = left_tree.query_min(1, x)
            min_right = right_tree.query_min(x, N)
            candidates = [walk_cost]
            if min_left < INF:
                candidates.append(min_left + x)
            if min_right < INF:
                candidates.append(min_right - x)
            res = min(candidates)
            output.append(str(res))
        else:
            x = int(parts[1])
            c = int(parts[2])
            ptr += 3
            if c < min_c[x]:
                min_c[x] = c
                left_val = c - x
                right_val = c + x
                left_tree.update(x, left_val)
                right_tree.update(x, right_val)
    
    print('\n'.join(output))

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