結果
問題 |
No.924 紲星
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:49:49 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,403 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 230,100 KB |
最終ジャッジ日時 | 2025-06-12 20:51:38 |
合計ジャッジ時間 | 8,054 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 10 |
ソースコード
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()