結果

問題 No.2065 Sum of Min
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:20:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,534 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,960 KB
実行使用メモリ 187,500 KB
最終ジャッジ日時 2025-03-20 20:22:19
合計ジャッジ時間 30,244 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.sorted = []
        self.prefix = []

def build(arr, l, r):
    node = SegmentTreeNode(l, r)
    if l == r:
        node.sorted = [arr[l]]
        node.prefix = [arr[l]]
    else:
        mid = (l + r) // 2
        node.left = build(arr, l, mid)
        node.right = build(arr, mid+1, r)
        # Merge the sorted arrays of left and right children
        node.sorted = []
        i = j = 0
        left_sorted = node.left.sorted
        right_sorted = node.right.sorted
        len_left = len(left_sorted)
        len_right = len(right_sorted)
        while i < len_left and j < len_right:
            if left_sorted[i] <= right_sorted[j]:
                node.sorted.append(left_sorted[i])
                i += 1
            else:
                node.sorted.append(right_sorted[j])
                j += 1
        # Add remaining elements
        if i < len_left:
            node.sorted.extend(left_sorted[i:])
        elif j < len_right:
            node.sorted.extend(right_sorted[j:])
        # Compute prefix sums
        total = 0
        node.prefix = []
        for num in node.sorted:
            total += num
            node.prefix.append(total)
    return node

def query_segment(node, l, r, x):
    if node.r < l or node.l > r:
        return (0, 0)
    if l <= node.l and node.r <= r:
        idx = bisect.bisect_right(node.sorted, x)
        sum_le = node.prefix[idx-1] if idx > 0 else 0
        return (sum_le, idx)
    sum_le = 0
    cnt = 0
    if node.left:
        s, c = query_segment(node.left, l, r, x)
        sum_le += s
        cnt += c
    if node.right:
        s, c = query_segment(node.right, l, r, x)
        sum_le += s
        cnt += c
    return (sum_le, cnt)

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
    # Build the segment tree
    root = build(A, 0, N-1)
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        l = L - 1  # Convert to 0-based
        r = R - 1
        sum_le, cnt_le = query_segment(root, l, r, X)
        total = r - l + 1
        sum_min = sum_le + X * (total - cnt_le)
        print(sum_min)

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