結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2020-03-27 08:57:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 384 ms / 2,000 ms |
コード長 | 2,163 bytes |
コンパイル時間 | 367 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 127,144 KB |
最終ジャッジ日時 | 2025-01-02 08:17:08 |
合計ジャッジ時間 | 21,146 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesclass BinaryIndexedTree():def __init__(self, seq):self.size = len(seq)self.depth = self.size.bit_length()self.build(seq)def build(self, seq):data = seqsize = self.sizefor i, x in enumerate(data):j = i + (i & (-i))if j < size:data[j] += data[i]self.data = datadef __repr__(self):return self.data.__repr__()def get_sum(self, i):data = self.datas = 0while i:s += data[i]i -= i & -ireturn sdef add(self, i, x):data = self.datasize = self.sizewhile i < size:data[i] += xi += i & -idef find_kth_element(self, k):data = self.datasize = self.sizex, sx = 0, 0dx = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):dx = (1 << i)if x + dx >= size:continuey = x + dxsy = sx + data[y]if sy < k:x, sx = y, syreturn x + 1N, K, *A = map(int, read().split())sortedA = sorted(set(A))elem_rank = {x: i for i, x in enumerate(sortedA, 1)}bit_num = BinaryIndexedTree([0] * (N + 10))bit_sum = BinaryIndexedTree([0] * (N + 10))total = 0for x in A[:K - 1]:r = elem_rank[x]bit_num.add(r, 1)bit_sum.add(r, x)total += xanswer = 10 ** 15for add_x, rm_x in zip(A[K - 1:], A):add_r = elem_rank[add_x]rm_r = elem_rank[rm_x]bit_num.add(add_r, 1)bit_sum.add(add_r, add_x)total += add_xn = (K + 1) // 2median_r = bit_num.find_kth_element(n)median = sortedA[median_r - 1]nl = bit_num.get_sum(median_r)nr = K - nlsl = bit_sum.get_sum(median_r)sr = total - slcost = (nl * median - sl) + (sr - nr * median)if answer > cost:answer = costbit_num.add(rm_r, -1)bit_sum.add(rm_r, -rm_x)total -= rm_xprint(answer)