結果

問題 No.924 紲星
ユーザー lam6er
提出日時 2025-04-16 01:11:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,066 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 294,972 KB
最終ジャッジ日時 2025-04-16 01:13:07
合計ジャッジ時間 7,580 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N
    queries = []
    for _ in range(Q):
        L = int(data[ptr]) - 1
        R = int(data[ptr+1]) - 1
        queries.append((L, R))
        ptr += 2

    # Build the segment tree
    size = 1
    while size < N:
        size <<= 1
    tree = [[] for _ in range(2 * size)]
    for i in range(N):
        tree[size + i] = [A[i]]
    for i in range(size + N, 2 * size):
        tree[i] = []
    # Merge nodes from bottom up
    for i in range(size - 1, 0, -1):
        left = tree[2 * i]
        right = tree[2 * i + 1]
        merged = []
        l_ptr = r_ptr = 0
        while l_ptr < len(left) and r_ptr < len(right):
            if left[l_ptr] <= right[r_ptr]:
                merged.append(left[l_ptr])
                l_ptr += 1
            else:
                merged.append(right[r_ptr])
                r_ptr += 1
        merged.extend(left[l_ptr:])
        merged.extend(right[r_ptr:])
        tree[i] = merged

    # Build prefix sums for each node
    prefix_sums = []
    for node in tree:
        ps = [0]
        s = 0
        for num in node:
            s += num
            ps.append(s)
        prefix_sums.append(ps)

    # Process each query
    for L, R in queries:
        nodes = []
        l = L + size
        r = R + size
        while l <= r:
            if l % 2 == 1:
                nodes.append(l)
                l += 1
            if r % 2 == 0:
                nodes.append(r)
                r -= 1
            l >>= 1
            r >>= 1

        # Determine the k-th element (median)
        m = R - L + 1
        k = (m + 1) // 2
        segs = [tree[node] for node in nodes]

        # Find min and max possible values in the query range
        min_val = float('inf')
        max_val = -float('inf')
        for node in nodes:
            if not tree[node]:
                continue
            min_val = min(min_val, tree[node][0])
            max_val = max(max_val, tree[node][-1])

        low, high = min_val, max_val
        answer = high
        while low <= high:
            mid = (low + high) // 2
            cnt = 0
            for seg in segs:
                cnt += bisect.bisect_right(seg, mid)
            if cnt >= k:
                answer = mid
                high = mid - 1
            else:
                low = mid + 1
        x = answer

        # Calculate sum_low and sum_high
        sum_low = 0
        cnt_low = 0
        sum_total = 0
        for node in nodes:
            seg = tree[node]
            ps = prefix_sums[node]
            pos = bisect.bisect_right(seg, x)
            sum_low += ps[pos]
            cnt_low += pos
            sum_total += ps[-1]

        sum_high = sum_total - sum_low
        cnt_high = m - cnt_low

        result = x * cnt_low - sum_low + (sum_high - x * cnt_high)
        print(result)

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