#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
コンパイル時間	231 ms
コンパイル使用メモリ	12,928 KB
実行使用メモリ	26,100 KB
最終ジャッジ日時	2024-04-20 10:04:53
合計ジャッジ時間	80,750 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 11,136 KB
testcase_01	AC	29 ms 11,136 KB
testcase_02	AC	29 ms 11,136 KB
testcase_03	AC	33 ms 11,136 KB
testcase_04	AC	28 ms 11,136 KB
testcase_05	AC	65 ms 11,520 KB
testcase_06	AC	71 ms 11,648 KB
testcase_07	AC	58 ms 11,520 KB
testcase_08	AC	41 ms 11,264 KB
testcase_09	AC	34 ms 11,136 KB
testcase_10	AC	28 ms 11,136 KB
testcase_11	AC	39 ms 11,392 KB
testcase_12	AC	32 ms 11,136 KB
testcase_13	AC	58 ms 11,392 KB
testcase_14	AC	37 ms 11,264 KB
testcase_15	AC	1,629 ms 22,028 KB
testcase_16	AC	1,565 ms 22,160 KB
testcase_17	AC	1,825 ms 22,540 KB
testcase_18	AC	1,961 ms 22,164 KB
testcase_19	TLE	-
testcase_20	AC	1,616 ms 22,184 KB
testcase_21	TLE	-
testcase_22	AC	1,804 ms 22,528 KB
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	AC	35 ms 11,264 KB
testcase_26	AC	34 ms 11,264 KB
testcase_27	AC	36 ms 11,392 KB
testcase_28	AC	36 ms 11,392 KB
testcase_29	AC	36 ms 11,264 KB
testcase_30	AC	34 ms 11,264 KB
testcase_31	AC	37 ms 11,392 KB
testcase_32	AC	37 ms 11,264 KB
testcase_33	AC	35 ms 11,264 KB
testcase_34	AC	34 ms 11,264 KB
testcase_35	AC	33 ms 11,264 KB
testcase_36	AC	34 ms 11,264 KB
testcase_37	AC	35 ms 11,264 KB
testcase_38	AC	35 ms 11,264 KB
testcase_39	AC	36 ms 11,264 KB
testcase_40	AC	36 ms 11,264 KB
testcase_41	AC	36 ms 11,136 KB
testcase_42	AC	35 ms 11,392 KB
testcase_43	AC	35 ms 11,264 KB
testcase_44	AC	34 ms 11,392 KB
testcase_45	AC	1,759 ms 23,832 KB
testcase_46	AC	1,495 ms 22,704 KB
testcase_47	AC	1,382 ms 23,312 KB
testcase_48	AC	1,456 ms 22,652 KB
testcase_49	AC	1,258 ms 22,676 KB
testcase_50	AC	1,263 ms 22,984 KB
testcase_51	AC	1,630 ms 23,456 KB
testcase_52	AC	1,396 ms 22,812 KB
testcase_53	AC	1,428 ms 23,104 KB
testcase_54	AC	1,437 ms 23,524 KB
testcase_55	AC	1,625 ms 23,496 KB
testcase_56	AC	1,487 ms 23,288 KB
testcase_57	AC	1,382 ms 22,640 KB
testcase_58	AC	1,439 ms 23,072 KB
testcase_59	AC	1,505 ms 23,472 KB
testcase_60	AC	1,397 ms 23,404 KB
testcase_61	AC	1,437 ms 23,376 KB
testcase_62	AC	1,388 ms 22,696 KB
testcase_63	AC	1,616 ms 23,796 KB
testcase_64	AC	1,456 ms 23,432 KB
testcase_65	AC	55 ms 19,436 KB
testcase_66	AC	57 ms 19,888 KB
testcase_67	AC	1,353 ms 24,660 KB
testcase_68	AC	1,302 ms 24,912 KB
testcase_69	AC	1,961 ms 25,348 KB
testcase_70	AC	1,532 ms 26,096 KB
testcase_71	AC	297 ms 13,544 KB
testcase_72	AC	264 ms 21,248 KB
testcase_73	AC	234 ms 21,336 KB
testcase_74	AC	291 ms 21,588 KB
testcase_75	AC	1,775 ms 25,100 KB
testcase_76	AC	1,504 ms 25,876 KB
testcase_77	TLE	-
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	AC	1,485 ms 25,308 KB
testcase_81	AC	1,791 ms 24,972 KB
testcase_82	TLE	-
testcase_83	AC	334 ms 18,496 KB
testcase_84	AC	351 ms 18,308 KB
testcase_85	AC	1,976 ms 25,768 KB
testcase_86	AC	1,775 ms 24,712 KB
testcase_87	AC	558 ms 25,084 KB
testcase_88	AC	537 ms 23,704 KB
testcase_89	AC	28 ms 11,136 KB
testcase_90	AC	28 ms 11,136 KB
testcase_91	AC	27 ms 11,136 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

結果

テストケース

ソースコード