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

提出ソース

結果

問題	No.738 平らな農地
ユーザー	terasa
提出日時	2023-01-09 00:45:50
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,004 ms / 2,000 ms
コード長	8,134 bytes
コンパイル時間	839 ms
コンパイル使用メモリ	87,336 KB
実行使用メモリ	161,448 KB
最終ジャッジ日時	2023-08-22 08:44:58
合計ジャッジ時間	50,205 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	168 ms 80,360 KB
testcase_01	AC	166 ms 80,368 KB
testcase_02	AC	167 ms 80,408 KB
testcase_03	AC	169 ms 80,264 KB
testcase_04	AC	170 ms 80,336 KB
testcase_05	AC	275 ms 85,972 KB
testcase_06	AC	270 ms 86,092 KB
testcase_07	AC	260 ms 86,052 KB
testcase_08	AC	227 ms 83,572 KB
testcase_09	AC	204 ms 83,120 KB
testcase_10	AC	188 ms 82,352 KB
testcase_11	AC	224 ms 83,752 KB
testcase_12	AC	204 ms 83,088 KB
testcase_13	AC	266 ms 85,112 KB
testcase_14	AC	208 ms 83,168 KB
testcase_15	AC	628 ms 147,748 KB
testcase_16	AC	650 ms 149,448 KB
testcase_17	AC	682 ms 149,004 KB
testcase_18	AC	684 ms 147,392 KB
testcase_19	AC	768 ms 155,680 KB
testcase_20	AC	644 ms 149,708 KB
testcase_21	AC	720 ms 155,724 KB
testcase_22	AC	675 ms 150,020 KB
testcase_23	AC	707 ms 152,384 KB
testcase_24	AC	723 ms 150,228 KB
testcase_25	AC	211 ms 82,860 KB
testcase_26	AC	215 ms 83,240 KB
testcase_27	AC	214 ms 83,204 KB
testcase_28	AC	211 ms 82,848 KB
testcase_29	AC	212 ms 82,736 KB
testcase_30	AC	213 ms 83,116 KB
testcase_31	AC	211 ms 83,068 KB
testcase_32	AC	209 ms 82,792 KB
testcase_33	AC	211 ms 83,128 KB
testcase_34	AC	209 ms 82,956 KB
testcase_35	AC	207 ms 82,828 KB
testcase_36	AC	213 ms 82,924 KB
testcase_37	AC	209 ms 82,744 KB
testcase_38	AC	216 ms 83,376 KB
testcase_39	AC	213 ms 83,368 KB
testcase_40	AC	211 ms 82,884 KB
testcase_41	AC	215 ms 83,096 KB
testcase_42	AC	207 ms 82,892 KB
testcase_43	AC	211 ms 83,056 KB
testcase_44	AC	214 ms 83,480 KB
testcase_45	AC	683 ms 155,092 KB
testcase_46	AC	667 ms 148,804 KB
testcase_47	AC	666 ms 158,368 KB
testcase_48	AC	639 ms 151,464 KB
testcase_49	AC	645 ms 150,432 KB
testcase_50	AC	652 ms 158,356 KB
testcase_51	AC	693 ms 153,740 KB
testcase_52	AC	665 ms 150,912 KB
testcase_53	AC	672 ms 157,600 KB
testcase_54	AC	687 ms 153,716 KB
testcase_55	AC	688 ms 153,676 KB
testcase_56	AC	684 ms 158,388 KB
testcase_57	AC	657 ms 146,572 KB
testcase_58	AC	661 ms 158,448 KB
testcase_59	AC	666 ms 155,332 KB
testcase_60	AC	682 ms 160,316 KB
testcase_61	AC	667 ms 159,788 KB
testcase_62	AC	644 ms 149,252 KB
testcase_63	AC	718 ms 155,152 KB
testcase_64	AC	692 ms 160,232 KB
testcase_65	AC	848 ms 149,508 KB
testcase_66	AC	877 ms 154,024 KB
testcase_67	AC	637 ms 151,196 KB
testcase_68	AC	628 ms 152,656 KB
testcase_69	AC	757 ms 154,248 KB
testcase_70	AC	689 ms 154,732 KB
testcase_71	AC	355 ms 113,248 KB
testcase_72	AC	340 ms 109,468 KB
testcase_73	AC	330 ms 109,864 KB
testcase_74	AC	360 ms 112,392 KB
testcase_75	AC	734 ms 150,372 KB
testcase_76	AC	675 ms 152,872 KB
testcase_77	AC	776 ms 149,176 KB
testcase_78	AC	811 ms 154,796 KB
testcase_79	AC	799 ms 154,872 KB
testcase_80	AC	700 ms 153,852 KB
testcase_81	AC	734 ms 150,616 KB
testcase_82	AC	750 ms 152,956 KB
testcase_83	AC	405 ms 105,360 KB
testcase_84	AC	377 ms 105,148 KB
testcase_85	AC	1,004 ms 161,448 KB
testcase_86	AC	903 ms 148,844 KB
testcase_87	AC	561 ms 153,836 KB
testcase_88	AC	539 ms 150,876 KB
testcase_89	AC	169 ms 80,236 KB
testcase_90	AC	170 ms 80,388 KB
testcase_91	AC	169 ms 80,384 KB

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

ソースコード

raw source code

from typing import List, Tuple, Callable, TypeVar, Optional
import sys
import itertools
import heapq
import bisect
import math
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key

input = sys.stdin.readline

if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)


def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input()[:-1]
def readlist1(): return list(map(lambda x: int(x) - 1, input().split()))


class BIT:
    def __init__(self, N):
        self.N = N
        self.A = [0] * (N + 1)

    def add(self, i, x):
        """add x to i-th element (0-indexed)"""
        assert 0 <= i < self.N
        i += 1
        while i <= self.N:
            self.A[i] += x
            i += i & -i

    def sum(self, i):
        """return sum(A[:i])"""
        assert 0 <= i <= self.N
        s = 0
        while i > 0:
            s += self.A[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        """return sum(A[l:r])"""
        return self.sum(r) - self.sum(l)



class BitVector:
    # reference: https://tiramister.net/blog/posts/bitvector/
    TABLE = bytes([
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    ])

    def __init__(self, N):
        self.cnum = (N + 255) >> 8

        self.bit = bytearray(self.cnum << 5)
        self.chunk = [0] * (self.cnum + 1)
        self.blocks = bytearray(self.cnum << 5)

        self.built = False

    def set(self, pos):
        self.bit[pos >> 3] |= 1 << (pos & 7)

    def access(self, pos):
        return self.bit[pos >> 3] >> (pos & 7) & 1

    def popcount(self, num):
        return self.TABLE[num]

    def build(self):
        for i in range(self.cnum):
            k = i << 5
            for j in range(31):
                self.blocks[k + 1] = self.blocks[k] + self.popcount(self.bit[k])
                k += 1
            self.chunk[i + 1] = self.chunk[i] + self.blocks[k] + self.popcount(self.bit[k])
        self.built = True

    def rank(self, pos):
        assert self.built
        cpos, tmp = pos >> 8, pos & 255
        bpos, offset = tmp >> 3, tmp & 7

        i = cpos << 5 | bpos
        rest = self.bit[i] & ((1 << offset) - 1)
        return self.chunk[cpos] + self.blocks[i] + self.popcount(rest)

    def select(self, num):
        """return minimum i that satisfies rank(i) = num"""
        assert self.built
        if num == 0:
            return 0
        if self.rank(self.N) < num:
            return -1

        l = -1
        r = self.N
        while r - l > 1:
            c = (l + r) >> 1
            if self.rank(c) >= num:
                r = c
            else:
                l = c
        return r


class WaveletMatrix:
    # reference: https://miti-7.hatenablog.com/entry/2018/04/28/152259
    def __init__(self, A):
        self.nums = sorted(set(A))
        self.idx = {a: i for i, a in enumerate(self.nums)}
        self.A = [self.idx[a] for a in A]

        self.digit = (len(self.nums) - 1).bit_length()
        self.B = [None] * self.digit
        self.offset = [None] * self.digit
        self.start_index = [-1] * len(self.nums)

        T = self.A
        for k in range(self.digit)[::-1]:
            self.B[k] = BitVector(len(T) + 1)
            zeros = []
            ones = []
            for i, a in enumerate(T):
                if a >> k & 1:
                    self.B[k].set(i)
                    ones.append(a)
                else:
                    zeros.append(a)
            self.B[k].build()
            self.offset[k] = len(zeros)
            T = zeros + ones
        for i, a in enumerate(T):
            if self.start_index[a] < 0:
                self.start_index[a] = i

    def access(self, i):
        """return i-th value"""
        ret = 0
        cur = i
        for k in range(self.digit)[::-1]:
            if self.B[k].access(cur):
                ret |= (1 << k)
                cur = self.B[k].rank(cur) + self.offset[k]
            else:
                cur -= self.B[k].rank(cur)
        return self.nums[ret]

    def rank(self, i, x):
        """return the number of x's in [0, i) range"""
        x = self.idx.get(x)
        if x is None:
            return 0
        for k in range(self.digit)[::-1]:
            if x >> k & 1:
                i = self.B[k].rank(i) + self.offset[k]
            else:
                i -= self.B[k].rank(i)
        return i - self.start_index[x]

    def quantile(self, l, r, n):
        """return n-th (0-indexed) smallest value in [l, r) range"""
        assert 0 <= n < r - l
        ret = 0
        for k in range(self.digit)[::-1]:
            rank_l = self.B[k].rank(l)
            rank_r = self.B[k].rank(r)
            ones = rank_r - rank_l
            zeros = r - l - ones
            if zeros <= n:
                ret |= 1 << k
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
                n -= zeros
            else:
                l -= rank_l
                r -= rank_r
        return self.nums[ret]

    def range_freq(self, l, r, lower, upper):
        """return the number of values s.t. lower <= x < upper"""
        return self.range_freq_upper(l, r, upper) - self.range_freq_upper(l, r, lower)

    def prev_value(self, l, r, upper):
        """return maximum x s.t. x < upper in [l, r) range if exist, otherwise None"""
        cnt = self.range_freq_upper(l, r, upper)
        if cnt == 0:
            return None
        return self.quantile(l, r, cnt - 1)

    def next_value(self, l, r, lower):
        """return minimum x s.t. x >= lower in [l, r) range if exist, otherwise None"""
        cnt = self.range_freq_upper(l, r, lower)
        if cnt == r - l:
            return None
        return self.quantile(l, r, cnt)

    def range_freq_upper(self, l, r, upper):
        """return the number of values s.t. x < upper in [l, r) range"""
        if l >= r:
            return 0
        if upper > self.nums[-1]:
            return r - l
        if upper <= self.nums[0]:
            return 0
        upper = bisect.bisect_left(self.nums, upper)
        ret = 0
        for k in range(self.digit)[::-1]:
            rank_l = self.B[k].rank(l)
            rank_r = self.B[k].rank(r)
            ones = rank_r - rank_l
            zeros = r - l - ones
            if upper >> k & 1:
                ret += zeros
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
            else:
                l -= rank_l
                r -= rank_r
        return ret



N, K = readints()
A = readlist()
WM = WaveletMatrix(A)

cands = [0] * (N - K + 1)
task = defaultdict(list)
for i in range(N - K + 1):
    med = WM.quantile(i, i + K, K // 2)
    task[med].append(i)

nums = WM.nums
idx = defaultdict(list)
for i, a in enumerate(A):
    idx[a].append(i)

bit = BIT(N)
bit2 = BIT(N)
for k in nums:
    for i in task[k]:
        cands[i] += k * bit2.range_sum(i, i + K) - bit.range_sum(i, i + K)
    for i in idx[k]:
        bit.add(i, k)
        bit2.add(i, 1)
bit = BIT(N)
bit2 = BIT(N)
for k in nums[::-1]:
    for i in task[k]:
        cands[i] += bit.range_sum(i, i + K) - k * bit2.range_sum(i, i + K)
    for i in idx[k]:
        bit.add(i, k)
        bit2.add(i, 1)
print(min(cands))

yukicoder

結果

テストケース

ソースコード