結果

問題 No.2065 Sum of Min
ユーザー lam6er
提出日時 2025-03-31 17:33:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,397 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 191,080 KB
最終ジャッジ日時 2025-03-31 17:34:23
合計ジャッジ時間 32,916 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.elements = []
        self.prefix_sums = [0]

def build_tree(arr, start, end):
    node = SegmentTreeNode(start, end)
    if start == end:
        node.elements = [arr[start]]
        node.prefix_sums.append(arr[start])
    else:
        mid = (start + end) // 2
        node.left = build_tree(arr, start, mid)
        node.right = build_tree(arr, mid+1, end)
        # Merge sorted lists
        i = j = 0
        left_elements = node.left.elements
        right_elements = node.right.elements
        node.elements = []
        while i < len(left_elements) and j < len(right_elements):
            if left_elements[i] <= right_elements[j]:
                node.elements.append(left_elements[i])
                i += 1
            else:
                node.elements.append(right_elements[j])
                j += 1
        node.elements.extend(left_elements[i:])
        node.elements.extend(right_elements[j:])
        # Compute prefix sums
        total = 0
        node.prefix_sums = [0]
        for num in node.elements:
            total += num
            node.prefix_sums.append(total)
    return node

def query_sum_count(node, L, R, X):
    if node.end < L or node.start > R:
        return (0, 0)
    if L <= node.start and node.end <= R:
        idx = bisect.bisect_right(node.elements, X)
        sum_val = node.prefix_sums[idx]
        count = idx
        return (sum_val, count)
    left_sum, left_count = query_sum_count(node.left, L, R, X)
    right_sum, right_count = query_sum_count(node.right, L, R, X)
    return (left_sum + right_sum, left_count + right_count)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    root = build_tree(A, 0, N-1)
    for _ in range(Q):
        L = int(input[ptr]) - 1
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        sum_low, count_low = query_sum_count(root, L, R, X)
        total_elements = R - L + 1
        count_high = total_elements - count_low
        print(sum_low + X * count_high)

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