結果

問題 No.2065 Sum of Min
ユーザー lam6er
提出日時 2025-04-15 23:41:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,177 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 186,672 KB
最終ジャッジ日時 2025-04-15 23:43:25
合計ジャッジ時間 34,511 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from heapq import merge
import sys

class SegmentTreeNode:
    __slots__ = ['l', 'r', 'left', 'right', 'sorted_list', 'prefix_sum']
    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 = SegmentTreeNode(l, r)
    if l == r:
        node.sorted_list = [A[l]]
        node.prefix_sum = [0, A[l]]
    else:
        mid = (l + r) // 2
        node.left = build(l, mid, A)
        node.right = build(mid + 1, r, A)
        # Merge the sorted lists using heapq.merge
        node.sorted_list = list(merge(node.left.sorted_list, node.right.sorted_list))
        # Compute prefix sums
        prefix = [0]
        current = 0
        for num in node.sorted_list:
            current += num
            prefix.append(current)
        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:
        # Binary search in the sorted_list
        idx = bisect.bisect_right(node.sorted_list, X)
        return (idx, node.prefix_sum[idx])
    else:
        left_count, left_sum = query(node.left, L, R, X)
        right_count, right_sum = query(node.right, L, R, X)
        return (left_count + right_count, left_sum + right_sum)

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
    # Compute prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    # Build segment tree
    root = build(0, N-1, A)
    # Process queries
    for _ in range(Q):
        L = int(input[ptr]) - 1
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        total_count = R - L + 1
        sum_total = prefix[R+1] - prefix[L]
        count_less, sum_less = query(root, L, R, X)
        answer = sum_less + X * (total_count - count_less)
        print(answer)

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