結果

問題 No.2065 Sum of Min
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:42:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,520 ms / 2,000 ms
コード長 2,102 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 184,332 KB
最終ジャッジ日時 2025-04-15 23:45:54
合計ジャッジ時間 23,645 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import heapq
import sys

class Node:
    __slots__ = ['start', 'end', 'left', 'right', 'sorted_list', 'prefix_sum']
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.sorted_list = []
        self.prefix_sum = []

def build_segment_tree(arr):
    def build(start, end):
        node = Node(start, end)
        if start == end:
            node.sorted_list = [arr[start]]
            prefix = [0, arr[start]]
            node.prefix_sum = prefix
        else:
            mid = (start + end) // 2
            node.left = build(start, mid)
            node.right = build(mid + 1, end)
            merged = list(heapq.merge(node.left.sorted_list, node.right.sorted_list))
            node.sorted_list = merged
            prefix = [0]
            s = 0
            for num in merged:
                s += num
                prefix.append(s)
            node.prefix_sum = prefix
        return node
    return build(0, len(arr) - 1)

def query_sum_leq_x(root, L, R, X):
    sum_leq = 0
    count_leq = 0
    stack = [root]
    while stack:
        node = stack.pop()
        if node.end < L or node.start > R:
            continue
        if L <= node.start and node.end <= R:
            idx = bisect.bisect_right(node.sorted_list, X)
            sum_leq += node.prefix_sum[idx]
            count_leq += idx
        else:
            stack.append(node.right)
            stack.append(node.left)
    return sum_leq, count_leq

def main():
    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_segment_tree(A)
    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_leq, count_leq = query_sum_leq_x(root, L, R, X)
        total = sum_leq + X * ( (R - L + 1) - count_leq )
        print(total)

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