結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー timi
提出日時 2025-10-06 10:44:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,682 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 127,568 KB
最終ジャッジ日時 2025-10-06 10:45:49
合計ジャッジ時間 74,908 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 25 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K,D=map(int, input().split())
A=list(map(int, input().split()))
E={}
B=sorted(list(set(A)))
for i in range(len(B)):
  E[B[i]]=i

class SegTree:
    n = 1
    size = 1
    log = 2
    d = [0]
    op = None

    def __init__(self,OP,E,V):
        self.n = len(V)
        self.op = OP
        self.e = E
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        return self.d[p + self.size]

    def prod(self, l, r):
        assert 0 <= l and l <= r and r <= self.n
        sml = self.e
        smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                smr = self.op(self.d[r - 1], smr)
                r -= 1
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def max_right(self, l, f):
        #assert 0 <= l and l <= self.n
        #assert f(self.e)
        if l == self.n:
            return self.n
        l += self.size
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not (f(self.op(sm, self.d[l]))):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                break
        return self.n

    def min_left(self, r, f):
        #assert 0 <= r and r <= self.n
        #assert f(self.e)
        if r == 0:
            return 0
        r += self.size
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not (f(self.op(self.d[r], sm))):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                break
        return 0

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def __str__(self):
        return str([self.get(i) for i in range(self.n)])


def op(a,b):
  return a+b
  
import bisect
st=SegTree(op,0,[0]*(N+10))
st2=SegTree(op,0,[0]*(N+10))
ans=10**20
for i in range(N):
  a=E[A[i]]
  now=st.get(a)
  st.set(a,now+A[i])
  
  now=st2.get(a)
  st2.set(a,now+1)
  
  if i+1>=K:
    l,r=-1,10**9+1
    while r-l>1:
      mid=(l+r)//2 
      z=bisect.bisect_left(B,mid)
      p=st2.prod(0,z) 
      z=bisect.bisect_right(B,mid+D)
      q=st2.prod(z,N+5)
      if p-q>0:
        r=mid 
      else:
        l=mid
    cnt=0
    z=bisect.bisect_left(B,mid)
    p=st.prod(0,z) 
    q=st2.prod(0,z) 
    cnt+=mid*q-p
    
    z=bisect.bisect_right(B,mid+D)
    p=st.prod(z,N+5)
    q=st2.prod(z,N+5)
    cnt+=p-mid*q
    ans=min(ans,cnt)
    j=i-K+1
    a=E[A[j]]
    now=st.get(a)
    st.set(a,now+A[j])
    now=st2.get(a)
    st2.set(a,now-1)
print(ans)
0