結果

問題 No.2065 Sum of Min
ユーザー lam6er
提出日時 2025-04-15 23:39:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,988 ms / 2,000 ms
コード長 2,289 bytes
コンパイル時間 486 ms
コンパイル使用メモリ 81,760 KB
実行使用メモリ 188,016 KB
最終ジャッジ日時 2025-04-15 23:41:06
合計ジャッジ時間 27,968 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import sys

class Node:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.sorted_list = []
        self.prefix_sum = []

def build(l, r, A):
    node = Node(l, r)
    if l == r:
        node.sorted_list = [A[l-1]]
        node.prefix_sum = [0, A[l-1]]
    else:
        mid = (l + r) // 2
        node.left = build(l, mid, A)
        node.right = build(mid + 1, r, A)
        # Merge the sorted lists of left and right children
        merged = []
        i = j = 0
        left_list = node.left.sorted_list
        right_list = node.right.sorted_list
        while i < len(left_list) and j < len(right_list):
            if left_list[i] <= right_list[j]:
                merged.append(left_list[i])
                i += 1
            else:
                merged.append(right_list[j])
                j += 1
        merged.extend(left_list[i:])
        merged.extend(right_list[j:])
        node.sorted_list = merged
        # Compute prefix sums
        prefix = [0]
        current_sum = 0
        for num in merged:
            current_sum += num
            prefix.append(current_sum)
        node.prefix_sum = prefix
    return node

def query(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_list, X)
        sum_leq = node.prefix_sum[idx]
        count_leq = idx
        return (sum_leq, count_leq)
    else:
        sum_left, count_left = query(node.left, L, R, X)
        sum_right, count_right = query(node.right, L, R, X)
        return (sum_left + sum_right, count_left + count_right)

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
    # Build the segment tree
    root = build(1, N, A)
    # Process each query
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        sum_leq, count_leq = query(root, L, R, X)
        total = sum_leq + X * (R - L + 1 - count_leq)
        print(total)

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