結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー sasa8uyauya
提出日時 2025-10-11 13:07:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,881 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 165,068 KB
最終ジャッジ日時 2025-10-11 13:08:40
合計ジャッジ時間 83,372 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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=n
      while ng-ok>1:
        m=(ok+ng)//2
        if self.st.sum(m,self.n)!=0:
          ok=m
        else:
          ng=m
    else:
      ok=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([(v,i) for i in range(n) for v in [a[i]-D,a[i]]]+[(-X,-1),(X,-1)])
pl.add((-X,-1))
pr=FakeMultiset([(v,i) for i in range(n) for v in [a[i]-D,a[i]]]+[(-X,-1),(X,-1)])
pr.add((X,-1))
h=0
for i in range(n):
  v=a[i]
  l,r=(v-D,i),(v,i)
  rr=pr.pop(0)
  if l[0]<=rr[0]:
    pr.add(rr)
    pl.add(l)
  else:
    h+=l[0]-rr[0]
    pl.add(rr)
    pr.add(l)
  ll=pl.pop(1)
  if ll[0]<=r[0]:
    pl.add(ll)
    pr.add(r)
  else:
    h+=ll[0]-r[0]
    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,j),(v,j)
  ll=pl.pop(1)
  if l[0]<=ll[0]:
    pl.add(ll)
    pl.remove(l)
  else:
    h-=l[0]-ll[0]
    pr.remove(l)
    pr.add(ll)
  rr=pr.pop(0)
  if rr[0]<=r[0]:
    pr.add(rr)
    pr.remove(r)
  else:
    h-=rr[0]-r[0]
    pl.remove(r)
    pl.add(rr)
print(ans)
0