結果
問題 |
No.3303 Heal Slimes 2
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)