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

提出ソース

結果

問題	No.738 平らな農地
ユーザー	terasa
提出日時	2023-01-10 19:40:33
言語	PyPy3 (7.3.15)
結果	AC
実行時間	606 ms / 2,000 ms
コード長	10,921 bytes
コンパイル時間	549 ms
コンパイル使用メモリ	86,968 KB
実行使用メモリ	160,628 KB
最終ジャッジ日時	2023-08-23 10:18:53
合計ジャッジ時間	37,395 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	166 ms 80,432 KB
testcase_01	AC	166 ms 80,284 KB
testcase_02	AC	167 ms 80,472 KB
testcase_03	AC	167 ms 80,188 KB
testcase_04	AC	168 ms 80,448 KB
testcase_05	AC	251 ms 84,712 KB
testcase_06	AC	230 ms 84,640 KB
testcase_07	AC	228 ms 85,108 KB
testcase_08	AC	212 ms 83,552 KB
testcase_09	AC	205 ms 82,980 KB
testcase_10	AC	193 ms 82,352 KB
testcase_11	AC	216 ms 83,640 KB
testcase_12	AC	200 ms 82,816 KB
testcase_13	AC	226 ms 84,852 KB
testcase_14	AC	203 ms 83,028 KB
testcase_15	AC	488 ms 153,028 KB
testcase_16	AC	510 ms 154,196 KB
testcase_17	AC	530 ms 155,740 KB
testcase_18	AC	513 ms 154,264 KB
testcase_19	AC	525 ms 156,108 KB
testcase_20	AC	499 ms 156,840 KB
testcase_21	AC	526 ms 156,120 KB
testcase_22	AC	507 ms 154,348 KB
testcase_23	AC	523 ms 154,692 KB
testcase_24	AC	521 ms 157,636 KB
testcase_25	AC	199 ms 83,192 KB
testcase_26	AC	205 ms 82,824 KB
testcase_27	AC	200 ms 83,272 KB
testcase_28	AC	198 ms 83,116 KB
testcase_29	AC	199 ms 82,960 KB
testcase_30	AC	201 ms 83,212 KB
testcase_31	AC	201 ms 82,988 KB
testcase_32	AC	199 ms 82,796 KB
testcase_33	AC	203 ms 83,004 KB
testcase_34	AC	200 ms 83,012 KB
testcase_35	AC	203 ms 83,116 KB
testcase_36	AC	205 ms 83,012 KB
testcase_37	AC	204 ms 83,012 KB
testcase_38	AC	206 ms 82,952 KB
testcase_39	AC	203 ms 82,980 KB
testcase_40	AC	211 ms 83,228 KB
testcase_41	AC	206 ms 83,176 KB
testcase_42	AC	208 ms 83,292 KB
testcase_43	AC	201 ms 82,832 KB
testcase_44	AC	204 ms 83,028 KB
testcase_45	AC	527 ms 158,652 KB
testcase_46	AC	494 ms 155,560 KB
testcase_47	AC	497 ms 157,256 KB
testcase_48	AC	468 ms 155,888 KB
testcase_49	AC	471 ms 154,140 KB
testcase_50	AC	475 ms 157,524 KB
testcase_51	AC	506 ms 156,524 KB
testcase_52	AC	490 ms 154,032 KB
testcase_53	AC	500 ms 158,900 KB
testcase_54	AC	508 ms 157,392 KB
testcase_55	AC	502 ms 156,876 KB
testcase_56	AC	516 ms 158,388 KB
testcase_57	AC	481 ms 154,324 KB
testcase_58	AC	489 ms 158,896 KB
testcase_59	AC	492 ms 158,840 KB
testcase_60	AC	490 ms 157,992 KB
testcase_61	AC	484 ms 156,936 KB
testcase_62	AC	485 ms 156,288 KB
testcase_63	AC	529 ms 158,612 KB
testcase_64	AC	492 ms 157,172 KB
testcase_65	AC	454 ms 156,272 KB
testcase_66	AC	457 ms 155,232 KB
testcase_67	AC	510 ms 154,272 KB
testcase_68	AC	514 ms 155,828 KB
testcase_69	AC	606 ms 159,316 KB
testcase_70	AC	551 ms 158,384 KB
testcase_71	AC	207 ms 102,648 KB
testcase_72	AC	210 ms 101,592 KB
testcase_73	AC	207 ms 103,896 KB
testcase_74	AC	208 ms 103,856 KB
testcase_75	AC	555 ms 154,744 KB
testcase_76	AC	536 ms 156,144 KB
testcase_77	AC	563 ms 151,016 KB
testcase_78	AC	601 ms 159,728 KB
testcase_79	AC	543 ms 160,628 KB
testcase_80	AC	501 ms 159,340 KB
testcase_81	AC	545 ms 156,228 KB
testcase_82	AC	443 ms 156,692 KB
testcase_83	AC	332 ms 114,244 KB
testcase_84	AC	284 ms 113,536 KB
testcase_85	AC	533 ms 156,620 KB
testcase_86	AC	499 ms 156,144 KB
testcase_87	AC	387 ms 155,592 KB
testcase_88	AC	371 ms 159,212 KB
testcase_89	AC	165 ms 80,332 KB
testcase_90	AC	165 ms 80,440 KB
testcase_91	AC	167 ms 80,212 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

結果

テストケース

ソースコード