結果
| 問題 | No.3303 Heal Slimes 2 | 
| コンテスト | |
| ユーザー |  sepa38 | 
| 提出日時 | 2025-09-26 22:41:55 | 
| 言語 | PyPy3 (7.3.15) | 
| 結果 | 
                                RE
                                 
                             | 
| 実行時間 | - | 
| コード長 | 1,844 bytes | 
| コンパイル時間 | 334 ms | 
| コンパイル使用メモリ | 82,508 KB | 
| 実行使用メモリ | 123,416 KB | 
| 最終ジャッジ日時 | 2025-09-26 22:43:27 | 
| 合計ジャッジ時間 | 7,155 ms | 
| ジャッジサーバーID (参考情報) | judge4 / judge2 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| other | RE * 30 | 
ソースコード
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, x) > cnt.prod(u, n):
      r = piv
    else:
      l = piv
    # print(l, r)
  x = di_inv[r]
  y = x + d
  u = bisect.bisect_right(sorted_h, y)
  res = (cnt.prod(0, r) * x - st.prod(0, r)) + (st.prod(u, n) - y * cnt.prod(u, n))
  # print((r, u), (x, y), res)
  # print((cnt.prod(0, r), 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)
            
            
            
        