結果

問題 No.3116 More and more teleporter
ユーザー k-kuwata
提出日時 2025-05-23 07:36:36
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,881 ms / 2,000 ms
コード長 3,152 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 28,744 KB
最終ジャッジ日時 2025-05-23 07:36:57
合計ジャッジ時間 17,181 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Using sys.stdin.readline for faster input
input = sys.stdin.readline

# Segment Tree for Min Query, Point Update
# 0-indexed internally for array access
class SegTree:
    def __init__(self, n_elements, identity_element=float('inf')):
        self.n = n_elements 
        self.identity = identity_element
        self.num_leaves = 1
        while self.num_leaves < self.n:
            self.num_leaves *= 2
        self.tree = [self.identity] * (2 * self.num_leaves)

    def update(self, pos, value):
        idx = pos + self.num_leaves
        
        if value >= self.tree[idx]: # Optimization: if new value is not better, do nothing
            return
        
        self.tree[idx] = value
        
        while idx > 1:
            idx //= 2
            self.tree[idx] = min(self.tree[idx * 2], self.tree[idx * 2 + 1])

    # Query range [query_l, query_r) (0-indexed, query_r is exclusive)
    def query(self, query_l, query_r):
        if query_l >= query_r: 
            return self.identity
            
        res = self.identity
        l = query_l + self.num_leaves
        r = query_r + self.num_leaves
        
        while l < r:
            if l & 1: 
                res = min(res, self.tree[l])
                l += 1
            if r & 1: 
                r -= 1
                res = min(res, self.tree[r])
            l //= 2
            r //= 2
        return res

def main():
    N, Q = map(int, input().split())

    st_minus = SegTree(N) # For c_i - i (1-indexed i)
    st_plus = SegTree(N)  # For c_i + i (1-indexed i)

    results = []

    for _ in range(Q):
        query_parts = list(map(int, input().split()))
        query_type = query_parts[0]

        if query_type == 1:
            target_x_1idx = query_parts[1] # 1-indexed target cell
            
            cost_walk = target_x_1idx - 1
            ans = cost_walk

            target_x_0idx = target_x_1idx - 1

            # Query for min(c_j - j) for j (1-indexed) in [1, target_x_1idx]
            # Corresponds to 0-indexed positions [0, target_x_0idx]
            # Segment tree query is [L, R), so query(0, target_x_0idx + 1)
            val_from_st_minus = st_minus.query(0, target_x_0idx + 1)
            if val_from_st_minus != float('inf'):
                ans = min(ans, val_from_st_minus + target_x_1idx)

            # Query for min(c_j + j) for j (1-indexed) in [target_x_1idx, N]
            # Corresponds to 0-indexed positions [target_x_0idx, N-1]
            # Segment tree query is [L, R), so query(target_x_0idx, N)
            val_from_st_plus = st_plus.query(target_x_0idx, N)
            if val_from_st_plus != float('inf'):
                ans = min(ans, val_from_st_plus - target_x_1idx)
            
            results.append(str(ans))

        elif query_type == 2:
            tele_x_1idx, tele_c = query_parts[1], query_parts[2] # 1-indexed position, cost
            tele_x_0idx = tele_x_1idx - 1

            st_minus.update(tele_x_0idx, tele_c - tele_x_1idx)
            st_plus.update(tele_x_0idx, tele_c + tele_x_1idx)

    sys.stdout.write("\n".join(results) + "\n")

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