結果
問題 | No.1248 Kth Sum |
ユーザー |
👑 |
提出日時 | 2022-06-30 04:01:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 951 ms / 2,000 ms |
コード長 | 4,092 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 126,676 KB |
最終ジャッジ日時 | 2024-11-23 20:10:12 |
合計ジャッジ時間 | 10,741 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
"""部分列の個数 -> MM = 1:自明M = 2:1個目 [K, 2K - 1]2個目 [2K, N]M = 3:1個目 [K, 3K - 2]2個目 [2K, N]3個目 [3K, N]M = M:1個目 [K, M(K - 1) + 1]x個目 [xK, N][xk, N] の部分を流用して全探索?"""class SegTree:def __init__(self, n, e, ope, lst=[]):self.N0 = 2 ** (n - 1).bit_length()self.e = eself.ope = opeself.data = [e] * (2 * self.N0)if lst:for i in range(n):self.data[self.N0 + i] = lst[i]for i in range(self.N0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def build(self):for i in range(self.N0 - 1, 0, -1):self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def update(self, i, x): #a_iの値をxに更新i += self.N0self.data[i] = xwhile i > 1:i >>= 1self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])def add(self, i, x):self.update(i, x + self.get(i))def set(self, i, x):self.data[self.N0 + i] = xdef query(self, l, r): #区間[l, r)での演算結果if r <= l:return self.elres = self.erres = self.el += self.N0r += self.N0while l < r:if l & 1:lres = self.ope(lres, self.data[l])l += 1if r & 1:r -= 1rres = self.ope(self.data[r], rres)l >>= 1r >>= 1return self.ope(lres, rres)def get(self, i): #a_iの値を返すreturn self.data[self.N0 + i]import heapqfrom heapq import *class Heapq:def __init__(self, lst = [], reverse = False):if reverse:self.pm = -1self.hq = [-l for l in lst]else:self.pm = 1self.hq = lst.copy()heapq.heapify(self.hq)self.tot = sum(lst)self.cnt = {}self.length = len(lst)def __bool__(self):return self.length > 0def __len__(self):return self.lengthdef __getitem__(self, i):if i == 0:return self.top()else:assert Falsedef push(self, x):self.length += 1self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1heapq.heappush(self.hq, x * self.pm)self.tot += xdef pop(self):if self.length == 0:return Noneself.length -= 1ret = heapq.heappop(self.hq)self.tot -= self.pm * retself.cnt[ret] -= 1self.delete()return self.pm * retdef top(self):if self.hq:return self.pm * self.hq[0]else:return Nonedef remove(self, x):if self.cnt.get(x * self.pm, 0) == 0:return Falseself.cnt[x * self.pm] -= 1self.length -= 1self.tot -= xself.delete()return Truedef delete(self):while self.hq and self.cnt.get(self.hq[0], 0) == 0:heapq.heappop(self.hq)n, k = map(int, input().split())A = list(map(int, input().split()))if k == 1:print(A[0])exit()inf = 1 << 30def ope(x, y):if x[0] <= y[0]:return xelse:return ye = (inf, -1)seg = SegTree(n, e, ope, [(a, i) for i, a in enumerate(A)])ans = A[k - 1]ind = Heapq()hq = []x = n // ktot = 0for i in range(x, 1, -1):a, i = seg.query(i * k - 1, n)ind.push(i)tot += aseg.update(i, e)hq.append((-a, i))heapify(hq)for i in range(x, 1, -1):mind = ind.top()if mind <= i * (k - 1):a = seg.query(k - 1, n)[0]ans = min(ans, tot + a)else:a = seg.query(k - 1, i * (k - 1) + 1)[0]ans = min(ans, tot + a)a, i = heappop(hq)tot += aseg.update(i, (-a, i))ind.remove(i)print(ans)