結果

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

ソースコード

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=0,10**9
    while r-l>1:
      mid=(l+r)//2 
      z=bisect.bisect_left(B,mid)
      p=mid*st2.prod(0,z)-st.prod(0,z) 
      
      z=bisect.bisect_right(B,mid+D)
      q=st.prod(z,N+5)-(mid+D)*st2.prod(z,N+5)
      if p-q>0:
        r=mid 
      else:
        l=mid
    ans=min(ans,p+q)
    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