結果

問題 No.924 紲星
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:49:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,637 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 77,732 KB
最終ジャッジ日時 2025-06-12 13:49:23
合計ジャッジ時間 7,262 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def merge(a, b):
    merged = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1
    merged.extend(a[i:])
    merged.extend(b[j:])
    return merged

def build_merge_sort_tree(A):
    tree = []
    current_level = []
    for num in A:
        sorted_list = [num]
        prefix_sums = [0, num]
        current_level.append((sorted_list, prefix_sums))
    tree.append(current_level)
    level = 0
    while len(current_level) > 1:
        next_level = []
        i = 0
        while i < len(current_level):
            if i + 1 < len(current_level):
                left_sorted, left_prefix = current_level[i]
                right_sorted, right_prefix = current_level[i + 1]
                merged_sorted = merge(left_sorted, right_sorted)
                merged_prefix = [0]
                s = 0
                for num in merged_sorted:
                    s += num
                    merged_prefix.append(s)
                next_level.append((merged_sorted, merged_prefix))
                i += 2
            else:
                next_level.append(current_level[i])
                i += 1
        tree.append(next_level)
        current_level = next_level
        level += 1
    return tree

def query_count_sum(tree, L, R, x):
    count = 0
    sum_val = 0
    root_level = len(tree) - 1
    stack = [(root_level, 0)]
    while stack:
        level, node_idx = stack.pop()
        if level >= len(tree):
            continue
        node_list = tree[level]
        if node_idx >= len(node_list):
            continue
        sorted_list, prefix_sums = node_list[node_idx]
        size = 1 << level
        start = node_idx * size
        end = start + size - 1
        if end < L or start > R:
            continue
        if L <= start and end <= R:
            pos = bisect.bisect_right(sorted_list, x)
            count += pos
            sum_val += prefix_sums[pos]
            continue
        if level == 0:
            if start >= L and start <= R:
                if sorted_list[0] <= x:
                    count += 1
                    sum_val += sorted_list[0]
        else:
            left_child = 2 * node_idx
            right_child = 2 * node_idx + 1
            stack.append((level - 1, right_child))
            stack.append((level - 1, left_child))
    return count, sum_val

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
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    B = sorted(A)
    tree = build_merge_sort_tree(A)
    for _ in range(Q):
        L = int(input[ptr]) - 1
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        len_sub = R - L + 1
        k = (len_sub + 1) // 2
        low = 0
        high = len(B) - 1
        answer_x = B[0]
        while low <= high:
            mid = (low + high) // 2
            x = B[mid]
            cnt, s = query_count_sum(tree, L, R, x)
            if cnt >= k:
                answer_x = x
                high = mid - 1
            else:
                low = mid + 1
        cnt_less, sum_less = query_count_sum(tree, L, R, answer_x)
        sum_total = prefix[R + 1] - prefix[L]
        sum_greater = sum_total - sum_less
        ans = answer_x * cnt_less - sum_less + (sum_greater - answer_x * (len_sub - cnt_less))
        print(ans)

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