#591809 (PyPy3) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	tktk_snsn
提出日時	2020-12-10 23:47:09
言語	PyPy3 (7.3.15)
結果	AC
実行時間	393 ms / 2,000 ms
コード長	1,802 bytes
コンパイル時間	1,729 ms
コンパイル使用メモリ	81,276 KB
実行使用メモリ	123,524 KB
最終ジャッジ日時	2023-10-20 01:02:31
合計ジャッジ時間	23,432 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	37 ms 53,380 KB
testcase_01	AC	38 ms 53,380 KB
testcase_02	AC	38 ms 53,380 KB
testcase_03	AC	38 ms 53,380 KB
testcase_04	AC	38 ms 53,380 KB
testcase_05	AC	85 ms 76,604 KB
testcase_06	AC	87 ms 76,680 KB
testcase_07	AC	90 ms 76,768 KB
testcase_08	AC	62 ms 72,772 KB
testcase_09	AC	56 ms 67,820 KB
testcase_10	AC	50 ms 63,612 KB
testcase_11	AC	63 ms 72,900 KB
testcase_12	AC	54 ms 65,676 KB
testcase_13	AC	85 ms 76,640 KB
testcase_14	AC	58 ms 69,864 KB
testcase_15	AC	299 ms 106,932 KB
testcase_16	AC	306 ms 110,404 KB
testcase_17	AC	332 ms 110,128 KB
testcase_18	AC	321 ms 106,656 KB
testcase_19	AC	355 ms 110,332 KB
testcase_20	AC	308 ms 110,376 KB
testcase_21	AC	364 ms 111,008 KB
testcase_22	AC	315 ms 110,384 KB
testcase_23	AC	354 ms 110,420 KB
testcase_24	AC	363 ms 110,384 KB
testcase_25	AC	57 ms 67,776 KB
testcase_26	AC	56 ms 67,784 KB
testcase_27	AC	58 ms 69,844 KB
testcase_28	AC	57 ms 67,788 KB
testcase_29	AC	59 ms 69,852 KB
testcase_30	AC	58 ms 67,784 KB
testcase_31	AC	56 ms 67,776 KB
testcase_32	AC	59 ms 69,852 KB
testcase_33	AC	57 ms 67,784 KB
testcase_34	AC	57 ms 67,788 KB
testcase_35	AC	55 ms 67,684 KB
testcase_36	AC	56 ms 67,788 KB
testcase_37	AC	59 ms 67,804 KB
testcase_38	AC	59 ms 69,840 KB
testcase_39	AC	60 ms 69,852 KB
testcase_40	AC	58 ms 69,844 KB
testcase_41	AC	59 ms 69,844 KB
testcase_42	AC	54 ms 65,628 KB
testcase_43	AC	55 ms 65,636 KB
testcase_44	AC	58 ms 67,788 KB
testcase_45	AC	310 ms 113,900 KB
testcase_46	AC	305 ms 109,144 KB
testcase_47	AC	311 ms 113,480 KB
testcase_48	AC	281 ms 113,156 KB
testcase_49	AC	280 ms 110,768 KB
testcase_50	AC	284 ms 113,480 KB
testcase_51	AC	314 ms 113,272 KB
testcase_52	AC	296 ms 110,768 KB
testcase_53	AC	302 ms 113,312 KB
testcase_54	AC	312 ms 113,504 KB
testcase_55	AC	315 ms 113,504 KB
testcase_56	AC	318 ms 113,468 KB
testcase_57	AC	290 ms 109,120 KB
testcase_58	AC	299 ms 113,352 KB
testcase_59	AC	293 ms 113,904 KB
testcase_60	AC	291 ms 113,864 KB
testcase_61	AC	296 ms 113,516 KB
testcase_62	AC	287 ms 109,132 KB
testcase_63	AC	321 ms 113,928 KB
testcase_64	AC	311 ms 113,516 KB
testcase_65	AC	59 ms 79,088 KB
testcase_66	AC	60 ms 79,188 KB
testcase_67	AC	252 ms 117,896 KB
testcase_68	AC	248 ms 122,228 KB
testcase_69	AC	315 ms 122,940 KB
testcase_70	AC	285 ms 123,072 KB
testcase_71	AC	204 ms 89,136 KB
testcase_72	AC	189 ms 89,840 KB
testcase_73	AC	178 ms 91,248 KB
testcase_74	AC	201 ms 91,308 KB
testcase_75	AC	299 ms 118,340 KB
testcase_76	AC	281 ms 123,140 KB
testcase_77	AC	307 ms 118,384 KB
testcase_78	AC	337 ms 123,524 KB
testcase_79	AC	321 ms 123,288 KB
testcase_80	AC	280 ms 122,904 KB
testcase_81	AC	296 ms 122,540 KB
testcase_82	AC	319 ms 123,192 KB
testcase_83	AC	254 ms 90,836 KB
testcase_84	AC	213 ms 90,588 KB
testcase_85	AC	393 ms 123,516 KB
testcase_86	AC	355 ms 118,024 KB
testcase_87	AC	195 ms 123,016 KB
testcase_88	AC	186 ms 118,096 KB
testcase_89	AC	37 ms 53,352 KB
testcase_90	AC	37 ms 53,352 KB
testcase_91	AC	36 ms 53,352 KB

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

ソースコード

raw source code

class fenwick_tree(object):
    def __init__(self, n):
        self.n = n
        self.log = n.bit_length()
        self.data = [0] * n

    def __sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def add(self, p, x):
        """ a[p] += xを行う"""
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        """a[l] + a[l+1] + .. + a[r-1]を返す"""
        return self.__sum(r) - self.__sum(l)

    def lower_bound(self, x):
        """a[0] + a[1] + .. a[i] >= x となる最小のiを返す"""
        if x <= 0:
            return -1
        i = 0
        k = 1 << self.log
        while k:
            if i + k <= self.n and self.data[i + k - 1] < x:
                x -= self.data[i + k - 1]
                i += k
            k >>= 1
        return i

    def show(self):
        for i in range(self.n):
            print(self.__sum(i+1) if not i else self.sum(i, i+1),  end=" ")
        print()


N, K = map(int, input().split())
A = list(map(int, input().split()))
if K == 1:
    print(0)
    exit()


Aset = sorted(set(A))
atoi = {a: i for i, a in enumerate(Aset)}
bit_cnt = fenwick_tree(N)
bit_val = fenwick_tree(N)

for i in range(K - 1):
    a = A[i]
    p = atoi[a]
    bit_cnt.add(p, 1)
    bit_val.add(p, a)

ans = 10 ** 18
for i in range(K - 1, N):
    a = A[i]
    p = atoi[a]
    bit_cnt.add(p, 1)
    bit_val.add(p, a)

    mid = bit_cnt.lower_bound((K + 1) // 2)
    a = Aset[mid]
    cost = a * bit_cnt.sum(0, mid) - bit_val.sum(0, mid)
    cost += bit_val.sum(mid + 1, N) - a * bit_cnt.sum(mid + 1, N)
    ans = min(ans, cost)

    a = A[i - K + 1]
    p = atoi[a]
    bit_cnt.add(p, -1)
    bit_val.add(p, -a)

print(ans)

yukicoder

結果

テストケース

ソースコード