結果

問題 No.924 紲星
ユーザー lam6er
提出日時 2025-04-16 16:49:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,444 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 81,704 KB
実行使用メモリ 423,432 KB
最終ジャッジ日時 2025-04-16 16:51:41
合計ジャッジ時間 7,479 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import sys

def build(l, r, A):
    node = {
        'start': l,
        'end': r,
        'left_child': None,
        'right_child': None,
        'sorted_list': [],
        'prefix_sum': [0]
    }
    if l == r:
        node['sorted_list'] = [A[l-1]]
        node['prefix_sum'] = [0, A[l-1]]
    else:
        mid = (l + r) // 2
        node['left_child'] = build(l, mid, A)
        node['right_child'] = build(mid+1, r, A)
        # Merge the two sorted lists
        left_list = node['left_child']['sorted_list']
        right_list = node['right_child']['sorted_list']
        merged = []
        i = j = 0
        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_sum
        prefix = [0]
        current_sum = 0
        for num in merged:
            current_sum += num
            prefix.append(current_sum)
        node['prefix_sum'] = prefix
    return node

def count_less_or_equal(node, L, R, x):
    if node['end'] < L or node['start'] > R:
        return 0
    if L <= node['start'] and node['end'] <= R:
        return bisect.bisect_right(node['sorted_list'], x)
    return count_less_or_equal(node['left_child'], L, R, x) + count_less_or_equal(node['right_child'], L, R, x)

def sum_less_or_equal(node, L, R, x):
    if node['end'] < L or node['start'] > R:
        return 0
    if L <= node['start'] and node['end'] <= R:
        idx = bisect.bisect_right(node['sorted_list'], x)
        return node['prefix_sum'][idx]
    return sum_less_or_equal(node['left_child'], L, R, x) + sum_less_or_equal(node['right_child'], L, R, x)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    queries = []
    for _ in range(Q):
        L = int(input[ptr])
        R = int(input[ptr+1])
        queries.append( (L, R) )
        ptr +=2
    
    # Precompute prefix sums for the original array.
    prefix_sum = [0]*(N+1)
    for i in range(1, N+1):
        prefix_sum[i] = prefix_sum[i-1] + A[i-1]
    
    # Build the segment tree.
    root = build(1, N, A)
    
    # Precompute sorted_A.
    sorted_A = sorted(A)
    
    # Process each query.
    for L, R in queries:
        len_sub = R - L + 1
        k = (len_sub +1) // 2
        
        # Binary search for m in sorted_A.
        low = 0
        high = len(sorted_A) -1
        answer_m = sorted_A[-1]
        while low <= high:
            mid = (low + high) //2
            m_candidate = sorted_A[mid]
            cnt = count_less_or_equal(root, L, R, m_candidate)
            if cnt >=k:
                answer_m = m_candidate
                high = mid -1
            else:
                low = mid +1
        m = answer_m
        
        # Compute count_lower and sum_lower.
        count_lower = count_less_or_equal(root, L, R, m)
        sum_lower = sum_less_or_equal(root, L, R, m)
        sum_total = prefix_sum[R] - prefix_sum[L-1]
        sum_abs = m * count_lower - sum_lower + (sum_total - sum_lower) - m * (len_sub - count_lower)
        print(sum_abs)

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