#287677 (Python3) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	しらっ亭
提出日時	2018-09-28 20:13:47
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 11,136 KB
testcase_01	AC	33 ms 11,136 KB
testcase_02	AC	33 ms 11,136 KB
testcase_03	AC	30 ms 11,264 KB
testcase_04	AC	30 ms 11,136 KB
testcase_05	AC	72 ms 11,520 KB
testcase_06	AC	79 ms 11,520 KB
testcase_07	AC	67 ms 11,520 KB
testcase_08	AC	47 ms 11,264 KB
testcase_09	AC	38 ms 11,136 KB
testcase_10	AC	33 ms 11,136 KB
testcase_11	AC	47 ms 11,264 KB
testcase_12	AC	38 ms 11,264 KB
testcase_13	AC	67 ms 11,392 KB
testcase_14	AC	42 ms 11,264 KB
testcase_15	AC	1,824 ms 21,932 KB
testcase_16	AC	1,726 ms 22,160 KB
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	AC	1,883 ms 22,188 KB
testcase_21	TLE	-
testcase_22	AC	1,954 ms 22,220 KB
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	AC	41 ms 11,264 KB
testcase_26	AC	41 ms 11,264 KB
testcase_27	AC	41 ms 11,264 KB
testcase_28	AC	42 ms 11,264 KB
testcase_29	AC	42 ms 11,264 KB
testcase_30	AC	41 ms 11,264 KB
testcase_31	AC	41 ms 11,264 KB
testcase_32	AC	40 ms 11,264 KB
testcase_33	AC	42 ms 11,264 KB
testcase_34	AC	40 ms 11,264 KB
testcase_35	AC	39 ms 11,264 KB
testcase_36	AC	39 ms 11,264 KB
testcase_37	AC	41 ms 11,264 KB
testcase_38	AC	41 ms 11,264 KB
testcase_39	AC	41 ms 11,392 KB
testcase_40	AC	41 ms 11,264 KB
testcase_41	AC	42 ms 11,392 KB
testcase_42	AC	40 ms 11,264 KB
testcase_43	AC	40 ms 11,264 KB
testcase_44	AC	41 ms 11,264 KB
testcase_45	AC	1,691 ms 23,788 KB
testcase_46	AC	1,683 ms 22,704 KB
testcase_47	AC	1,586 ms 23,416 KB
testcase_48	AC	1,528 ms 22,740 KB
testcase_49	AC	1,410 ms 22,612 KB
testcase_50	AC	1,465 ms 23,028 KB
testcase_51	AC	1,831 ms 23,376 KB
testcase_52	AC	1,670 ms 22,684 KB
testcase_53	AC	1,536 ms 22,932 KB
testcase_54	AC	1,711 ms 23,524 KB
testcase_55	AC	1,816 ms 23,620 KB
testcase_56	AC	1,670 ms 23,284 KB
testcase_57	AC	1,543 ms 22,468 KB
testcase_58	AC	1,597 ms 23,072 KB
testcase_59	AC	1,700 ms 23,592 KB
testcase_60	AC	1,625 ms 23,384 KB
testcase_61	AC	1,637 ms 23,376 KB
testcase_62	AC	1,624 ms 22,652 KB
testcase_63	AC	1,935 ms 23,720 KB
testcase_64	AC	1,688 ms 23,432 KB
testcase_65	AC	63 ms 19,436 KB
testcase_66	AC	65 ms 19,968 KB
testcase_67	AC	1,556 ms 24,668 KB
testcase_68	AC	1,518 ms 24,968 KB
testcase_69	TLE	-
testcase_70	AC	1,721 ms 25,968 KB
testcase_71	AC	336 ms 13,412 KB
testcase_72	AC	291 ms 21,248 KB
testcase_73	AC	258 ms 21,340 KB
testcase_74	AC	326 ms 21,456 KB
testcase_75	AC	1,997 ms 25,028 KB
testcase_76	AC	1,680 ms 25,884 KB
testcase_77	TLE	-
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	AC	1,679 ms 25,232 KB
testcase_81	TLE	-
testcase_82	TLE	-
testcase_83	AC	376 ms 18,488 KB
testcase_84	AC	390 ms 18,440 KB
testcase_85	TLE	-
testcase_86	TLE	-
testcase_87	AC	638 ms 25,132 KB
testcase_88	AC	608 ms 23,704 KB
testcase_89	AC	32 ms 11,008 KB
testcase_90	AC	32 ms 11,008 KB
testcase_91	AC	32 ms 11,008 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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())

yukicoder

結果

テストケース

ソースコード