結果

問題 No.1332 Range Nearest Query
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:28:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,830 ms / 2,500 ms
コード長 1,811 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 293,164 KB
最終ジャッジ日時 2025-03-31 17:29:23
合計ジャッジ時間 56,819 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    X = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    queries = []
    for _ in range(Q):
        l = int(input[ptr])
        r = int(input[ptr+1])
        x = int(input[ptr+2])
        queries.append((l-1, r-1, x))  # Convert to 0-based indices
        ptr += 3

    # Build the segment tree
    size = 1
    while size < N:
        size <<= 1
    seg = [[] for _ in range(2 * size)]

    # Initialize leaves
    for i in range(N):
        seg[size + i] = [X[i]]

    # Merge non-leaf nodes
    for i in range(size - 1, 0, -1):
        left = seg[2 * i]
        right = seg[2 * i + 1]
        merged = []
        l_ptr = r_ptr = 0
        while l_ptr < len(left) and r_ptr < len(right):
            if left[l_ptr] < right[r_ptr]:
                merged.append(left[l_ptr])
                l_ptr += 1
            else:
                merged.append(right[r_ptr])
                r_ptr += 1
        merged += left[l_ptr:]
        merged += right[r_ptr:]
        seg[i] = merged

    # Process each query
    for l, r, x in queries:
        res = float('inf')
        a = l + size
        b = r + size
        nodes = []
        while a <= b:
            if a % 2 == 1:
                nodes.append(seg[a])
                a += 1
            if b % 2 == 0:
                nodes.append(seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        for arr in nodes:
            pos = bisect.bisect_left(arr, x)
            if pos < len(arr):
                res = min(res, abs(arr[pos] - x))
            if pos > 0:
                res = min(res, abs(arr[pos - 1] - x))
        print(res)

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