結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー 已经死了
提出日時 2025-10-20 23:30:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 829 ms / 4,000 ms
コード長 1,442 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 148,904 KB
最終ジャッジ日時 2025-10-21 10:28:48
合計ジャッジ時間 20,045 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right
input=lambda:sys.stdin.readline().rstrip("\r\n")
MI=lambda:map(int,input().split())
li=lambda:list(MI())
ii=lambda:int(input())

class BIT:
    def __init__(self,n):
        self.n=n
        self.b=[0]*(n+1)
    def add(self,i,v):
        while i<=self.n:
            self.b[i]+=v
            i+=i&-i
    def sum(self,i):
        s=0
        while i>0:
            s+=self.b[i]
            i-=i&-i
        return s
    def kth(self,k):
        i=0
        p=1<<((self.n).bit_length()-1)
        while p:
            j=i+p
            if j<=self.n and self.b[j]<k:
                k-=self.b[j]
                i=j
            p>>=1
        return i+1

n,k,d=MI()
a=li()

hv=sorted(set(a))
uv=sorted(set(a+[x-d for x in a]))

bc=BIT(len(hv))
bs=BIT(len(hv))
bu=BIT(len(uv))

def add(x,sgn):
    i=bisect_left(hv,x)+1
    bc.add(i,sgn)
    bs.add(i,sgn*x)
    j=bisect_left(uv,x)+1
    bu.add(j,sgn)
    j2=bisect_left(uv,x-d)+1
    bu.add(j2,sgn)

tot=0
for i in range(k):
    x=a[i]
    add(x,1)
    tot+=x

def cur():
    L=uv[bu.kth(k)-1]
    iL=bisect_left(hv,L)
    lc=bc.sum(iL)
    ls=bs.sum(iL)
    R=L+d
    iR=bisect_right(hv,R)
    le=bc.sum(iR)
    se=bs.sum(iR)
    rc=k-le
    sr=tot-se
    return lc*L-ls+sr-rc*R

ans=cur()
l=0
for r in range(k,n):
    x=a[l]
    add(x,-1)
    tot-=x
    l+=1
    x=a[r]
    add(x,1)
    tot+=x
    v=cur()
    if v<ans: ans=v

print(ans)
0