結果

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

ソースコード

diff # 

import bisect

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

    B = 500
    blocks = []
    for i in range(0, N, B):
        end = min(i + B, N)
        block = A[i:end]
        block.sort()
        prefix = [0]
        s = 0
        for num in block:
            s += num
            prefix.append(s)
        blocks.append( (i, end-1, block, prefix) )

    min_val = min(A)
    max_val = max(A)

    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1

        M = R - L + 1
        k = (M - 1) // 2
        low = min_val
        high = max_val
        mid = 0

        while low <= high:
            mid = (low + high) // 2
            count = 0
            for block in blocks:
                start, end, sorted_arr, prefix = block
                if end < L or start > R:
                    continue
                if L <= start and end <= R:
                    cnt = bisect.bisect_right(sorted_arr, mid)
                    count += cnt
                else:
                    cnt = 0
                    left = L
                    right = R
                    left_pos = start
                    right_pos = end
                    for idx in range(len(sorted_arr)):
                        num = sorted_arr[idx]
                        pos = start + idx
                        if pos > right:
                            break
                        if pos >= left and num <= mid:
                            cnt += 1
                        else:
                            pass
                    count += cnt
            if count < k + 1:
                low = mid + 1
            else:
                high = mid - 1

        mid = low

        elements = []
        for i in range(L-1, R):
            elements.append(A[i])
        elements.sort()
        prefix = [0]
        s = 0
        for num in elements:
            s += num
            prefix.append(s)
        M_total = len(elements)
        k = (M_total - 1) // 2
        sum_left = elements[k] * (k+1) - prefix[k+1]
        sum_right = (prefix[M_total] - prefix[k+1]) - elements[k] * (M_total - k - 1)
        total = sum_left + sum_right
        print(total)

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