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

提出ソース

結果

問題	No.738 平らな農地
ユーザー	terasa
提出日時	2023-01-10 19:40:33
言語	PyPy3 (7.3.15)
結果	AC
実行時間	529 ms / 2,000 ms
コード長	10,921 bytes
コンパイル時間	290 ms
コンパイル使用メモリ	82,352 KB
実行使用メモリ	161,340 KB
最終ジャッジ日時	2024-06-01 07:56:00
合計ジャッジ時間	28,246 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	68 ms 70,820 KB
testcase_01	AC	68 ms 71,516 KB
testcase_02	AC	67 ms 72,132 KB
testcase_03	AC	68 ms 70,688 KB
testcase_04	AC	68 ms 71,172 KB
testcase_05	AC	141 ms 81,188 KB
testcase_06	AC	140 ms 80,988 KB
testcase_07	AC	133 ms 81,244 KB
testcase_08	AC	121 ms 79,712 KB
testcase_09	AC	109 ms 79,620 KB
testcase_10	AC	96 ms 78,488 KB
testcase_11	AC	118 ms 80,008 KB
testcase_12	AC	108 ms 79,224 KB
testcase_13	AC	132 ms 80,540 KB
testcase_14	AC	113 ms 79,416 KB
testcase_15	AC	393 ms 148,912 KB
testcase_16	AC	411 ms 152,280 KB
testcase_17	AC	431 ms 149,736 KB
testcase_18	AC	416 ms 147,388 KB
testcase_19	AC	426 ms 155,468 KB
testcase_20	AC	403 ms 150,616 KB
testcase_21	AC	437 ms 155,432 KB
testcase_22	AC	422 ms 152,024 KB
testcase_23	AC	434 ms 153,756 KB
testcase_24	AC	427 ms 152,404 KB
testcase_25	AC	106 ms 79,240 KB
testcase_26	AC	115 ms 79,596 KB
testcase_27	AC	111 ms 79,484 KB
testcase_28	AC	109 ms 79,424 KB
testcase_29	AC	108 ms 79,648 KB
testcase_30	AC	110 ms 79,788 KB
testcase_31	AC	109 ms 79,456 KB
testcase_32	AC	108 ms 79,648 KB
testcase_33	AC	110 ms 79,868 KB
testcase_34	AC	110 ms 79,368 KB
testcase_35	AC	110 ms 79,640 KB
testcase_36	AC	113 ms 79,576 KB
testcase_37	AC	109 ms 79,436 KB
testcase_38	AC	113 ms 79,728 KB
testcase_39	AC	110 ms 79,552 KB
testcase_40	AC	117 ms 79,488 KB
testcase_41	AC	112 ms 79,608 KB
testcase_42	AC	115 ms 79,384 KB
testcase_43	AC	111 ms 79,516 KB
testcase_44	AC	113 ms 79,768 KB
testcase_45	AC	434 ms 158,212 KB
testcase_46	AC	396 ms 151,696 KB
testcase_47	AC	417 ms 158,536 KB
testcase_48	AC	373 ms 152,888 KB
testcase_49	AC	378 ms 152,796 KB
testcase_50	AC	386 ms 158,212 KB
testcase_51	AC	413 ms 157,148 KB
testcase_52	AC	393 ms 152,516 KB
testcase_53	AC	406 ms 158,468 KB
testcase_54	AC	424 ms 157,064 KB
testcase_55	AC	406 ms 156,988 KB
testcase_56	AC	425 ms 158,928 KB
testcase_57	AC	386 ms 148,320 KB
testcase_58	AC	397 ms 159,236 KB
testcase_59	AC	406 ms 158,496 KB
testcase_60	AC	406 ms 158,244 KB
testcase_61	AC	398 ms 158,136 KB
testcase_62	AC	393 ms 150,160 KB
testcase_63	AC	445 ms 158,272 KB
testcase_64	AC	409 ms 157,792 KB
testcase_65	AC	363 ms 149,464 KB
testcase_66	AC	368 ms 154,220 KB
testcase_67	AC	407 ms 153,432 KB
testcase_68	AC	407 ms 155,948 KB
testcase_69	AC	505 ms 159,920 KB
testcase_70	AC	456 ms 160,120 KB
testcase_71	AC	112 ms 96,644 KB
testcase_72	AC	113 ms 97,792 KB
testcase_73	AC	115 ms 99,988 KB
testcase_74	AC	113 ms 99,804 KB
testcase_75	AC	465 ms 153,424 KB
testcase_76	AC	445 ms 156,324 KB
testcase_77	AC	489 ms 150,644 KB
testcase_78	AC	529 ms 160,296 KB
testcase_79	AC	470 ms 161,340 KB
testcase_80	AC	419 ms 156,840 KB
testcase_81	AC	449 ms 157,476 KB
testcase_82	AC	357 ms 156,728 KB
testcase_83	AC	229 ms 109,312 KB
testcase_84	AC	185 ms 109,044 KB
testcase_85	AC	438 ms 157,448 KB
testcase_86	AC	416 ms 155,052 KB
testcase_87	AC	296 ms 155,276 KB
testcase_88	AC	282 ms 155,340 KB
testcase_89	AC	67 ms 71,216 KB
testcase_90	AC	66 ms 70,456 KB
testcase_91	AC	65 ms 72,332 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 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: List[int], weight: List[int] = None):
        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.weight = weight
        if self.weight:
            self.S = [[0 for _ in range(len(self.A) + 1)] for _ in range(self.digit + 1)]
            for i, a in enumerate(self.A):
                self.S[self.digit][i + 1] = self.S[self.digit][i] + self.weight[i]

        if self.weight:
            T = list(zip(self.A, self.weight))
            for k in range(self.digit)[::-1]:
                self.B[k] = BitVector(len(T) + 1)
                zeros = []
                ones = []
                for i, (a, w) in enumerate(T):
                    if a >> k & 1:
                        self.B[k].set(i)
                        ones.append((a, w))
                    else:
                        zeros.append((a, w))
                self.B[k].build()
                self.offset[k] = len(zeros)
                T = zeros + ones
                for i, (a, w) in enumerate(T):
                    self.S[k][i + 1] = self.S[k][i] + w
        else:
            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

    def access(self, i: int):
        """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, l: int, r: int, x: int):
        """return the number of x's in [l, r) range"""
        x = self.idx.get(x)
        if x is None:
            return 0
        for k in range(self.digit)[::-1]:
            if x >> k & 1:
                l = self.B[k].rank(l) + self.offset[k]
                r = self.B[k].rank(r) + self.offset[k]
            else:
                l -= self.B[k].rank(l)
                r -= self.B[k].rank(r)
        return r - l

    def quantile(self, l: int, r: int, n: int):
        """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 rquantile(self, l: int, r: int, n: int):
        """return n-th (0-indeed) largest value in [l, r) range"""
        return self.quantile(l, r, r - l - 1 - n)

    def range_freq(self, l: int, r: int, lower: int, upper: int):
        """return the number of values s.t. lower <= x < upper in [l, r) range"""
        if lower >= upper:
            return 0
        return self._range_freq_upper(l, r, upper) - self._range_freq_upper(l, r, lower)

    def prev_value(self, l: int, r: int, upper: int):
        """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: int, r: int, lower: int):
        """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_sum(self, l: int, r: int, lower: int, upper: int):
        """return sum of values s.t. lower <= x < upper in [l, r) range
        must be constructed with weight
        """
        assert self.weight
        return self._range_sum_upper(l, r, upper) - self._range_sum_upper(l, r, lower)

    def range_nsmallest_sum(self, l: int, r: int, n: int):
        """return sum of the first n (**1-indexed**) values ordered by ascending order in [l, r) range
        must be constructed with weight
        """
        assert self.weight
        if l >= r:
            return 0
        if self.digit == 0:
            return self.nums[0] * n
        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 += self._get_internal_sum(k, l - rank_l, r - rank_r)
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
                n -= zeros
                if n == 0:
                    return ret
            else:
                l -= rank_l
                r -= rank_r
        ret += self._get_internal_sum(0, l, l + n)
        return ret

    def range_nlargest_sum(self, l: int, r: int, n: int):
        """return sum of the first n (**1-indexed**) values ordered by descending order in [l, r) range
        must be constructed with weight
        """
        assert self.weight
        return self._get_internal_sum(self.digit, l, r) - self.range_nsmallest_sum(l, r, r - l - n)

    def _range_freq_upper(self, l: int, r: int, upper: int):
        """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

    def _range_sum_upper(self, l: int, r: int, upper: int):
        """return sum of values s.t. x < upper in [l, r) range"""
        if l >= r:
            return 0
        if upper > self.nums[-1]:
            return self._get_internal_sum(self.digit, l, r)
        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
            zero = r - l - ones
            if upper >> k & 1:
                ret += self._get_internal_sum(k, l - rank_l,  r - rank_r)
                l = rank_l + self.offset[k]
                r = rank_r + self.offset[k]
            else:
                l -= rank_l
                r -= rank_r
        return ret

    def _get_internal_sum(self, k: int, l: int, r: int):
        return self.S[k][r] - self.S[k][l]


N, K = readints()
A = readlist()
W = WaveletMatrix(A, A)
ans = 1 << 50
for i in range(N - K + 1):
    v = W.range_nlargest_sum(i, i + K, K // 2) - W.range_nsmallest_sum(i, i + K, K // 2)
    ans = min(ans, v)
print(ans)

yukicoder

結果

テストケース

ソースコード