結果

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

ソースコード

diff # 

import bisect
import sys

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

def merge(left_list, right_list):
    merged = []
    i = j = 0
    len_left = len(left_list)
    len_right = len(right_list)
    while i < len_left and j < len_right:
        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:])
    return merged

def build(arr, l, r):
    node = SegmentTreeNode(l, r)
    if l == r:
        node.sorted_list = [arr[l]]
        node.prefix_sum = [0, arr[l]]
    else:
        mid = (l + r) // 2
        node.left = build(arr, l, mid)
        node.right = build(arr, mid + 1, r)
        node.sorted_list = merge(node.left.sorted_list, node.right.sorted_list)
        # Compute prefix sum
        prefix = [0]
        current_sum = 0
        for num in node.sorted_list:
            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:
        pos = bisect.bisect_right(node.sorted_list, X)
        sum_le = node.prefix_sum[pos]
        count_le = pos
        return (sum_le, count_le)
    else:
        left_sum, left_count = query(node.left, L, R, X)
        right_sum, right_count = query(node.right, L, R, X)
        return (left_sum + right_sum, left_count + right_count)

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(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_le, count_le = query(root, L, R, X)
        total = sum_le + X * ( (R - L + 1) - count_le )
        print(total)

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