結果

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

ソースコード

diff # 

import sys
import bisect

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

def build(l, r, A):
    node = SegmentTreeNode(l, r)
    if l == r:
        node.sorted_list = [A[l]]
        node.prefix_sums = [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
        left_list = node.left.sorted_list
        right_list = node.right.sorted_list
        node.sorted_list = []
        i = j = 0
        while i < len(left_list) and j < len(right_list):
            if left_list[i] < right_list[j]:
                node.sorted_list.append(left_list[i])
                i += 1
            else:
                node.sorted_list.append(right_list[j])
                j += 1
        node.sorted_list.extend(left_list[i:])
        node.sorted_list.extend(right_list[j:])
        # Compute prefix sums
        node.prefix_sums = [0]
        current_sum = 0
        for num in node.sorted_list:
            current_sum += num
            node.prefix_sums.append(current_sum)
    return node

def count_query(node, L, R, x):
    if node.r < L or node.l > R:
        return 0
    if L <= node.l and node.r <= R:
        return bisect.bisect_right(node.sorted_list, x)
    return count_query(node.left, L, R, x) + count_query(node.right, L, R, x)

def sum_query(node, L, R, x):
    if node.r < L or node.l > R:
        return 0
    if L <= node.l and node.r <= R:
        cnt = bisect.bisect_right(node.sorted_list, x)
        return node.prefix_sums[cnt]
    return sum_query(node.left, L, R, x) + sum_query(node.right, L, R, x)

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
    
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    
    root = build(0, N-1, A)
    
    sorted_unique = sorted(set(A))
    sorted_unique.sort()
    
    for _ in range(Q):
        L = int(input[ptr]) - 1
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        current_len = R - L + 1
        k = (current_len + 1) // 2
        
        low = 0
        high = len(sorted_unique) - 1
        answer = sorted_unique[-1]
        while low <= high:
            mid = (low + high) // 2
            x_candidate = sorted_unique[mid]
            cnt = count_query(root, L, R, x_candidate)
            if cnt >= k:
                answer = x_candidate
                high = mid - 1
            else:
                low = mid + 1
        median = answer
        
        cnt_less = count_query(root, L, R, median)
        sum_less = sum_query(root, L, R, median)
        sum_total = prefix[R+1] - prefix[L]
        sum_greater = sum_total - sum_less
        cnt_greater = current_len - cnt_less
        
        res = (median * cnt_less - sum_less) + (sum_greater - median * cnt_greater)
        print(res)

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