結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    idx +=2
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    queries = []
    for _ in range(Q):
        L = int(data[idx])-1
        R = int(data[idx+1])-1
        queries.append((L, R))
        idx +=2
    
    # Precompute prefix sums for the original array
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    
    # Coordinate compression
    sorted_A = sorted(A)
    B = sorted_A
    # Build pos and sum_pos for each value
    from collections import defaultdict
    pos_dict = defaultdict(list)
    for i, num in enumerate(A):
        pos_dict[num].append(i)
    # sorted unique values
    unique_B = sorted(pos_dict.keys())
    M = len(unique_B)
    # Precompute prefix sums for each unique value
    sum_B = [0]*(M+1)
    for i in range(M):
        sum_B[i+1] = sum_B[i] + unique_B[i] * len(pos_dict[unique_B[i]])
    
    # Function to find the median using binary search on unique_B
    for L, R in queries:
        length = R - L + 1
        k = (length +1) //2
        
        # Binary search to find the median value
        low = 0
        high = M-1
        answer = unique_B[-1]
        while low <= high:
            mid = (low + high) //2
            current_val = unique_B[mid]
            # Count numbers <= current_val in [L, R]
            cnt = 0
            left = 0
            right = mid
            best = mid
            while left <= right:
                m = (left + right) //2
                val = unique_B[m]
                indices = pos_dict[val]
                # find the number of elements in [L, R]
                l = bisect.bisect_left(indices, L)
                r = bisect.bisect_right(indices, R)
                c = r - l
                if val <= current_val:
                    cnt_mid = c
                    if val == current_val:
                        best = m
                        break
                    left = m +1
                else:
                    right = m -1
            # Now, best is the index of current_val in unique_B
            total =0
            for m in range(best+1):
                val = unique_B[m]
                indices = pos_dict[val]
                l = bisect.bisect_left(indices, L)
                r = bisect.bisect_right(indices, R)
                total += r - l
            if total >=k:
                answer = unique_B[mid]
                high = mid -1
            else:
                low = mid +1
        
        x = answer
        
        # Now compute sum_low: sum of elements <=x in [L, R]
        sum_low =0
        cnt_low =0
        left = bisect.bisect_left(unique_B, x)
        if left < M and unique_B[left] ==x:
            left +=1
        for m in range(left):
            val = unique_B[m]
            indices = pos_dict[val]
            l = bisect.bisect_left(indices, L)
            r = bisect.bisect_right(indices, R)
            c = r - l
            cnt_low +=c
            sum_low += val * c
        # Add elements equal to x
        if x in pos_dict:
            indices = pos_dict[x]
            l = bisect.bisect_left(indices, L)
            r = bisect.bisect_right(indices, R)
            c = r - l
            cnt_low +=c
            sum_low +=x *c
        
        sum_total = prefix[R+1] - prefix[L]
        sum_high = sum_total - sum_low
        cnt_high = (R - L +1) - cnt_low
        res = x * cnt_low - sum_low + (sum_high - x * cnt_high)
        print(res)

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