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

提出ソース

結果

問題	No.738 平らな農地
ユーザー	terasa
提出日時	2023-01-10 18:57:50
言語	PyPy3 (7.3.15)
結果	RE
実行時間	-
コード長	10,982 bytes
コンパイル時間	353 ms
コンパイル使用メモリ	82,312 KB
実行使用メモリ	161,796 KB
最終ジャッジ日時	2024-06-01 07:54:47
合計ジャッジ時間	32,295 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 70,632 KB
testcase_01	AC	71 ms 71,048 KB
testcase_02	AC	70 ms 70,772 KB
testcase_03	AC	67 ms 70,768 KB
testcase_04	AC	67 ms 70,884 KB
testcase_05	AC	157 ms 81,640 KB
testcase_06	AC	161 ms 81,736 KB
testcase_07	AC	156 ms 81,636 KB
testcase_08	AC	143 ms 80,176 KB
testcase_09	AC	119 ms 79,492 KB
testcase_10	AC	103 ms 79,192 KB
testcase_11	AC	134 ms 80,020 KB
testcase_12	AC	122 ms 79,592 KB
testcase_13	AC	151 ms 81,456 KB
testcase_14	AC	125 ms 79,864 KB
testcase_15	AC	452 ms 149,132 KB
testcase_16	AC	474 ms 151,864 KB
testcase_17	AC	503 ms 149,772 KB
testcase_18	AC	495 ms 147,388 KB
testcase_19	AC	526 ms 155,432 KB
testcase_20	AC	464 ms 150,020 KB
testcase_21	AC	516 ms 155,592 KB
testcase_22	AC	481 ms 152,024 KB
testcase_23	AC	521 ms 153,544 KB
testcase_24	AC	517 ms 152,144 KB
testcase_25	AC	122 ms 79,660 KB
testcase_26	AC	128 ms 80,412 KB
testcase_27	AC	128 ms 79,992 KB
testcase_28	AC	122 ms 79,928 KB
testcase_29	AC	124 ms 79,764 KB
testcase_30	AC	122 ms 79,500 KB
testcase_31	AC	119 ms 79,700 KB
testcase_32	AC	118 ms 80,040 KB
testcase_33	AC	123 ms 79,740 KB
testcase_34	AC	123 ms 79,932 KB
testcase_35	AC	121 ms 79,532 KB
testcase_36	AC	125 ms 80,072 KB
testcase_37	AC	122 ms 79,900 KB
testcase_38	AC	123 ms 80,000 KB
testcase_39	AC	127 ms 79,584 KB
testcase_40	AC	126 ms 80,256 KB
testcase_41	AC	119 ms 79,560 KB
testcase_42	AC	126 ms 79,800 KB
testcase_43	AC	121 ms 79,580 KB
testcase_44	AC	131 ms 79,904 KB
testcase_45	AC	469 ms 158,520 KB
testcase_46	AC	463 ms 151,744 KB
testcase_47	AC	458 ms 158,112 KB
testcase_48	AC	427 ms 153,068 KB
testcase_49	AC	436 ms 152,848 KB
testcase_50	AC	437 ms 158,224 KB
testcase_51	AC	478 ms 156,928 KB
testcase_52	AC	451 ms 152,700 KB
testcase_53	AC	454 ms 157,816 KB
testcase_54	AC	488 ms 157,156 KB
testcase_55	AC	472 ms 157,296 KB
testcase_56	AC	485 ms 158,856 KB
testcase_57	AC	439 ms 148,068 KB
testcase_58	AC	456 ms 159,284 KB
testcase_59	AC	458 ms 158,744 KB
testcase_60	AC	453 ms 158,472 KB
testcase_61	AC	461 ms 158,008 KB
testcase_62	AC	430 ms 150,516 KB
testcase_63	AC	482 ms 158,180 KB
testcase_64	AC	459 ms 157,768 KB
testcase_65	RE	-
testcase_66	RE	-
testcase_67	AC	487 ms 153,300 KB
testcase_68	AC	479 ms 156,372 KB
testcase_69	AC	635 ms 159,912 KB
testcase_70	AC	548 ms 160,516 KB
testcase_71	AC	114 ms 96,788 KB
testcase_72	AC	117 ms 97,504 KB
testcase_73	AC	120 ms 99,860 KB
testcase_74	AC	119 ms 100,216 KB
testcase_75	AC	568 ms 153,936 KB
testcase_76	AC	505 ms 156,380 KB
testcase_77	AC	596 ms 150,536 KB
testcase_78	AC	661 ms 160,540 KB
testcase_79	AC	578 ms 161,796 KB
testcase_80	AC	487 ms 156,584 KB
testcase_81	AC	530 ms 157,472 KB
testcase_82	AC	461 ms 156,800 KB
testcase_83	AC	276 ms 109,684 KB
testcase_84	AC	216 ms 109,924 KB
testcase_85	AC	558 ms 157,904 KB
testcase_86	AC	554 ms 155,520 KB
testcase_87	AC	306 ms 155,500 KB
testcase_88	AC	289 ms 155,404 KB
testcase_89	RE	-
testcase_90	AC	66 ms 71,744 KB
testcase_91	RE	-

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

ソースコード

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
        assert 1 <= n <= r - l
        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
        assert 1 <= n <= r - l
        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):
    med = W.quantile(i, i + K, K // 2)
    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

結果

テストケース

ソースコード