結果

問題 No.1332 Range Nearest Query
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:14:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,219 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,808 KB
実行使用メモリ 263,020 KB
最終ジャッジ日時 2025-03-20 21:15:42
合計ジャッジ時間 15,832 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 13 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import sys

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [[] for _ in range(4 * self.n)]  # Initialize with empty lists
        self.build(0, 0, self.n - 1, data)
    
    def build(self, node, l, r, data):
        if l == r:
            self.tree[node] = [data[l]]
            return
        mid = (l + r) // 2
        left_node = 2 * node + 1
        right_node = 2 * node + 2
        self.build(left_node, l, mid, data)
        self.build(right_node, mid + 1, r, data)
        # Merge the two sorted lists
        self.tree[node] = []
        i = j = 0
        left = self.tree[left_node]
        right = self.tree[right_node]
        len_left = len(left)
        len_right = len(right)
        while i < len_left and j < len_right:
            if left[i] < right[j]:
                self.tree[node].append(left[i])
                i += 1
            else:
                self.tree[node].append(right[j])
                j += 1
        self.tree[node].extend(left[i:])
        self.tree[node].extend(right[j:])
    
    def query(self, l, r, x):
        res = float('inf')
        def _query(node, node_l, node_r):
            nonlocal res
            if node_r < l or node_l > r:
                return
            if l <= node_l and node_r <= r:
                arr = self.tree[node]
                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))
                return
            mid = (node_l + node_r) // 2
            _query(2 * node + 1, node_l, mid)
            _query(2 * node + 2, mid + 1, node_r)
        _query(0, 0, self.n - 1)
        return res

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    X = list(map(int, data[ptr:ptr+N]))
    ptr += N
    st = SegmentTree(X)
    Q = int(data[ptr])
    ptr +=1
    for _ in range(Q):
        l = int(data[ptr]) -1
        r = int(data[ptr+1]) -1
        x = int(data[ptr+2])
        ptr +=3
        print(st.query(l, r, x))

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