結果

問題 No.3303 Heal Slimes 2
ユーザー sasa8uyauya
提出日時 2025-10-11 13:27:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,821 ms / 4,000 ms
コード長 1,763 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 143,384 KB
最終ジャッジ日時 2025-10-11 13:28:00
合計ジャッジ時間 40,584 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
  def __init__(self,n):
    self.n=n
    self.tree=[0]*(n+1)

  def add(self,i,x):
    i+=1
    while i<=self.n:
      self.tree[i]+=x
      i+=i&-i

  def _sum(self,i):
    res=0
    i+=1
    while i>0:
      res+=self.tree[i]
      i-=i&-i
    return res

  def sum(self,l,r):
    return self._sum(r-1)-self._sum(l-1)


class FakeMultiset:
  def __init__(self,a):
    self.z=sorted(a)
    self.d={v:i for i,v in enumerate(self.z)}
    self.n=len(self.z)
    self.st=BIT(self.n)
  
  def add(self,i):
    self.st.add(self.d[i],1)
  
  def remove(self,i):
    self.st.add(self.d[i],-1)
  
  def pop(self,f):
    if f:
      ok=-1
      ng=self.n
      while ng-ok>1:
        m=(ok+ng)//2
        if self.st.sum(m,self.n)!=0:
          ok=m
        else:
          ng=m
    else:
      ok=self.n
      ng=-1
      while ok-ng>1:
        m=(ok+ng)//2
        if self.st.sum(0,m+1)!=0:
          ok=m
        else:
          ng=m
    self.st.add(ok,-1)
    return self.z[ok]


n,K,D=map(int,input().split())
a=list(map(int,input().split()))
ans=sum(a)
X=10**10
pl=FakeMultiset([u for v in a for u in [v-D,v]]+[-X,X])
pl.add(-X)
pr=FakeMultiset([u for v in a for u in [v-D,v]]+[-X,X])
pr.add(X)
h=0
for i in range(n):
  v=a[i]
  l,r=v-D,v
  rr=pr.pop(0)
  if l<=rr:
    pr.add(rr)
    pl.add(l)
  else:
    h+=l-rr
    pl.add(rr)
    pr.add(l)
  ll=pl.pop(1)
  if ll<=r:
    pl.add(ll)
    pr.add(r)
  else:
    h+=ll-r
    pr.add(ll)
    pl.add(r)
  if i<K-1:
    continue
  ans=min(ans,h)
  j=i-(K-1)
  v=a[j]
  l,r=v-D,v
  ll=pl.pop(1)
  if l<=ll:
    pl.add(ll)
    pl.remove(l)
  else:
    h-=l-ll
    pr.remove(l)
    pr.add(ll)
  rr=pr.pop(0)
  if rr<=r:
    pr.add(rr)
    pr.remove(r)
  else:
    h-=rr-r
    pl.remove(r)
    pl.add(rr)
print(ans)
0