結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー sepa38
提出日時 2025-09-26 22:46:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,846 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 123,148 KB
最終ジャッジ日時 2025-09-26 22:46:58
合計ジャッジ時間 45,586 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect


class segt:
  def __init__(self, n, ele, calc):
    self.num = 2 ** (n - 1).bit_length()
    self.el = ele
    self.data = [ele] * (2 * self.num)
    self.calc = calc

  def update(self, idx, x):
    idx += self.num - 1
    self.data[idx] = x
    while idx > 0:
      idx = (idx - 1) // 2
      self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])
  
  def renew(self, idx, x):
    self.update(idx, self.calc(self.get(idx), x))

  def prod(self, left, right):
    l = left + self.num
    r = right + self.num
    res = self.el
    while l < r:
      if l % 2:
        res = self.calc(res, self.data[l-1])
        l += 1
      if r % 2:
        r -= 1
        res = self.calc(res, self.data[r-1])
      l //= 2
      r //= 2
    return res

  def get(self, idx):
    return self.data[idx+self.num-1]

def add(x, y):
  return x + y


n, k, d = map(int, input().split())
h = list(map(int, input().split()))
sorted_h = sorted(h)

st = segt(n, 0, add)
cnt = segt(n, 0, add)

di = dict()
di_inv = dict()
for v in sorted_h:
  if v in di:
    continue
  di[v] = len(di)
  di_inv[di[v]] = v

for v in h[:k]:
  st.renew(di[v], v)
  cnt.renew(di[v], 1)

ans = 1 << 60
for i in range(n-k+1):
  l, r = 0, n
  while r - l > 1:
    piv = (l + r) // 2
    x = di_inv[piv]
    u = bisect.bisect_right(sorted_h, x+d)
    # print(piv, u, x)
    if cnt.prod(0, piv) > cnt.prod(u, n):
      r = piv
    else:
      l = piv
    # print(l, r)
  x = di_inv[l]
  y = x + d
  u = bisect.bisect_right(sorted_h, y)
  res = (cnt.prod(0, l) * x - st.prod(0, l)) + (st.prod(u, n) - y * cnt.prod(u, n))
  # print((l, u), (x, y), res)
  # print((cnt.prod(0, l), cnt.prod(u, n)))
  ans = min(ans, res)

  if i < n - k:
    st.renew(di[h[i]], -h[i])
    cnt.renew(di[h[i]], -1)
    st.renew(di[h[i+k]], h[i+k])
    cnt.renew(di[h[i+k]], 1)

print(ans)
0