結果

問題 No.738 平らな農地
ユーザー しらっ亭
提出日時 2018-09-28 20:13:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,304 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 26,036 KB
最終ジャッジ日時 2024-10-12 05:32:57
合計ジャッジ時間 90,484 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 73 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import math


class FenwickTree:
    def __init__(self, n):
        # 0-indexed
        self.N = n
        self.bit = [0] * n
        self.M = 1 << int(math.ceil(math.log2(self.N)))

    def add(self, i, val):
        while i < self.N:
            self.bit[i] += val
            i |= i + 1

    def sum(self, n):
        """[0, n)"""
        ret = 0
        n -= 1
        while n >= 0:
            ret += self.bit[n]
            n = (n & (n + 1)) - 1
        return ret

    def sum_lr(self, l, r):
        """[l, r)"""
        return self.sum(r) - self.sum(l)

    def count_index(self, w):
        x = 0
        k = self.M - 1

        while True:
            if x + k < self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k + 1
            if k == 0:
                break
            k >>= 1
        return x


def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    if k == 1:
        return 0

    compressor = list(set(A))
    compressor.sort()

    def compress(x):
        return bisect.bisect_left(compressor, x)

    C = [compress(a) for a in A]
    m = len(compressor)

    counter = FenwickTree(m)

    for i in range(k):
        counter.add(C[i], 1)

    k2 = k // 2 + 1

    medians = []
    medians.append(counter.count_index(k2))
    for i in range(k, n):
        counter.add(C[i], 1)
        counter.add(C[i-k], -1)
        medians.append(counter.count_index(k2))

    ans = 1e18

    ft_cnt = FenwickTree(m)
    ft_sum = FenwickTree(m)

    for i in range(n):
        c = C[i]
        ft_cnt.add(c, 1)
        ft_sum.add(c, A[i])

        if i >= k:
            r = C[i - k]
            ft_cnt.add(r, -1)
            ft_sum.add(r, -A[i - k])

        if i >= k - 1:
            median_c = medians[i - k + 1]
            median = compressor[median_c]

            lower_cnt = ft_cnt.sum(median_c)
            lower_sum = ft_sum.sum(median_c)

            higher_cnt = ft_cnt.sum_lr(median_c, m)
            higher_sum = ft_sum.sum_lr(median_c, m)

            inc_cost = median * lower_cnt - lower_sum
            dec_cost = higher_sum - median * higher_cnt
            cand = inc_cost + dec_cost

            ans = min(ans, cand)
    return ans


if __name__ == '__main__':
    print(solve())
0