結果

問題 No.3303 Heal Slimes 2
ユーザー wasd314
提出日時 2025-10-05 15:46:15
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,341 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 170,692 KB
最終ジャッジ日時 2025-10-06 12:48:02
合計ジャッジ時間 14,375 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, n: int):
        self.n = n
        self.arr = [0] * (n + 1)
        # n以下の最大の2冪
        self.powlog_n = 2 ** (n.bit_length() - 1)

    def add(self, i: int, x: int):
        """`a[i] += x`

        Args:
            i (int): 0-indexed
            x (int): to add

        Note:
            If `i` is out of `[0, n)`, do nothing.
        """
        if i < 0:
            return
        i += 1
        arr = self.arr
        n = self.n
        while i <= n:
            arr[i] += x
            # arr[i] %= mod
            i += i & -i

    def sum(self, i: int) -> int:
        """get `sum(a[:i])`

        Args:
            i (int): 0-indexed

        Returns:
            int: `sum(a[:i])`
        """
        ans = 0
        arr = self.arr
        # mod = self.mod
        if i > self.n:
            i = self.n
        while i > 0:
            ans += arr[i]
            # ans %= mod
            i -= i & -i
        return ans

    def sum2(self, i: int, j: int) -> int:
        """get `sum(a[i:j])`

        Args:
            i (int): 0-indexed begin
            j (int): 0-indexed end

        Returns:
            int: `sum(a[i:j])`
        """
        ans = self.sum(j) - self.sum(i)
        # ans %= mod
        return ans

    def lower_bound(self, w: int) -> int:
        """lower_bound

        Args:
            w (int): sum

        Returns:
            int: min `x`(>= 0, 0-indexed)  s.t.  `sum(a[:x])` >= w
                `n + 1` if w > `sum(a[:n])`

        Note:
            expect `a[i]` >= 0 for all `i`

        Reference:
            http://hos.ac/slides/20140319_bit.pdf - p.75
        """
        if w <= 0:
            return 0
        arr = self.arr
        n = self.n
        k = self.powlog_n
        x = 0
        while k > 0:
            if x + k <= n and arr[x + k] < w:
                x += k
                w -= arr[x]
            k //= 2
        return x + 1

    def get(self, i: int):
        """index access `a[i]`

        Args:
            i (int): 0-indexed

        Returns:
            int | None: `a[i]` if 0 <= `i` < n
                else `None`
        """
        if 0 <= i < self.n:
            return self.sum2(i, i + 1)
        else:
            return None

    def __repr__(self) -> str:
        a = [self.get(i) for i in range(self.n)]
        a_s = " ".join(map(str, a))
        return f"FenwickTree({self.n})[{a_s}]"

n, k, d = map(lambda s_: int(s_), input().split())
h = tuple(map(lambda s_: int(s_), input().split()))
h += tuple(hi - d for hi in h)

def coordinate_compress(a, offset=0):
    sa = sorted(set(a))
    toi = {e: i for i, e in enumerate(sa, offset)}
    ha = tuple(toi[ai] for ai in a)
    return sa, toi, ha, len(toi)
sa, toi, ha, nn = coordinate_compress(h)

ft0 = FenwickTree(nn)
ft1 = FenwickTree(nn)

def cost():
    il = ft0.lower_bound(k)
    # l = sa[il]
    # ans = l * k - ft1.sum(il)
    # ans += ft1.sum2(il, nn) - l * k
    ans = ft1.sum2(il, nn) - ft1.sum(il)
    return ans

def push(i, c):
    ft0.add(ha[i], 1 * c)
    ft1.add(ha[i], h[i] * c)
    ft0.add(ha[n + i], 1 * c)
    ft1.add(ha[n + i], h[n + i] * c)


for i in range(k):
    push(i, 1)
ans = cost()

for r in range(k, n):
    push(r, 1)
    push(r - k, -1)
    ansi = cost()
    ans = min(ans, ansi)
ans = (ans - d * k) // 2
print(ans)
0