結果
問題 | No.738 平らな農地 |
ユーザー | terasa |
提出日時 | 2023-01-10 18:57:50 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 10,982 bytes |
コンパイル時間 | 266 ms |
コンパイル使用メモリ | 86,992 KB |
実行使用メモリ | 160,528 KB |
最終ジャッジ日時 | 2023-08-23 10:17:15 |
合計ジャッジ時間 | 41,817 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 161 ms
80,284 KB |
testcase_01 | AC | 163 ms
80,460 KB |
testcase_02 | AC | 161 ms
80,448 KB |
testcase_03 | AC | 162 ms
80,500 KB |
testcase_04 | AC | 162 ms
80,444 KB |
testcase_05 | AC | 276 ms
85,376 KB |
testcase_06 | AC | 255 ms
85,592 KB |
testcase_07 | AC | 244 ms
86,144 KB |
testcase_08 | AC | 232 ms
84,800 KB |
testcase_09 | AC | 205 ms
83,292 KB |
testcase_10 | AC | 193 ms
83,012 KB |
testcase_11 | AC | 218 ms
83,956 KB |
testcase_12 | AC | 212 ms
83,036 KB |
testcase_13 | AC | 239 ms
85,244 KB |
testcase_14 | AC | 215 ms
83,412 KB |
testcase_15 | AC | 536 ms
153,000 KB |
testcase_16 | AC | 555 ms
154,264 KB |
testcase_17 | AC | 593 ms
155,796 KB |
testcase_18 | AC | 575 ms
154,380 KB |
testcase_19 | AC | 619 ms
156,104 KB |
testcase_20 | AC | 545 ms
156,884 KB |
testcase_21 | AC | 598 ms
156,228 KB |
testcase_22 | AC | 572 ms
154,244 KB |
testcase_23 | AC | 597 ms
154,812 KB |
testcase_24 | AC | 601 ms
157,492 KB |
testcase_25 | AC | 208 ms
83,368 KB |
testcase_26 | AC | 214 ms
83,528 KB |
testcase_27 | AC | 217 ms
83,896 KB |
testcase_28 | AC | 211 ms
83,912 KB |
testcase_29 | AC | 209 ms
83,508 KB |
testcase_30 | AC | 208 ms
83,412 KB |
testcase_31 | AC | 206 ms
83,544 KB |
testcase_32 | AC | 204 ms
83,896 KB |
testcase_33 | AC | 213 ms
83,632 KB |
testcase_34 | AC | 209 ms
83,320 KB |
testcase_35 | AC | 211 ms
83,612 KB |
testcase_36 | AC | 214 ms
83,572 KB |
testcase_37 | AC | 216 ms
83,420 KB |
testcase_38 | AC | 209 ms
83,564 KB |
testcase_39 | AC | 209 ms
83,724 KB |
testcase_40 | AC | 211 ms
83,484 KB |
testcase_41 | AC | 210 ms
83,376 KB |
testcase_42 | AC | 218 ms
83,772 KB |
testcase_43 | AC | 212 ms
83,420 KB |
testcase_44 | AC | 221 ms
83,612 KB |
testcase_45 | AC | 553 ms
158,448 KB |
testcase_46 | AC | 548 ms
155,640 KB |
testcase_47 | AC | 541 ms
157,368 KB |
testcase_48 | AC | 500 ms
155,988 KB |
testcase_49 | AC | 522 ms
154,140 KB |
testcase_50 | AC | 522 ms
157,376 KB |
testcase_51 | AC | 564 ms
156,764 KB |
testcase_52 | AC | 534 ms
153,836 KB |
testcase_53 | AC | 540 ms
158,796 KB |
testcase_54 | AC | 565 ms
157,504 KB |
testcase_55 | AC | 559 ms
157,084 KB |
testcase_56 | AC | 566 ms
158,468 KB |
testcase_57 | AC | 535 ms
154,476 KB |
testcase_58 | AC | 533 ms
159,016 KB |
testcase_59 | AC | 538 ms
158,856 KB |
testcase_60 | AC | 533 ms
157,928 KB |
testcase_61 | AC | 541 ms
157,824 KB |
testcase_62 | AC | 513 ms
156,568 KB |
testcase_63 | AC | 571 ms
158,528 KB |
testcase_64 | AC | 546 ms
157,072 KB |
testcase_65 | RE | - |
testcase_66 | RE | - |
testcase_67 | AC | 579 ms
154,512 KB |
testcase_68 | AC | 575 ms
156,160 KB |
testcase_69 | AC | 713 ms
159,860 KB |
testcase_70 | AC | 633 ms
158,808 KB |
testcase_71 | AC | 201 ms
102,700 KB |
testcase_72 | AC | 203 ms
101,632 KB |
testcase_73 | AC | 209 ms
103,816 KB |
testcase_74 | AC | 205 ms
103,960 KB |
testcase_75 | AC | 645 ms
154,540 KB |
testcase_76 | AC | 605 ms
156,388 KB |
testcase_77 | AC | 692 ms
151,320 KB |
testcase_78 | AC | 743 ms
159,724 KB |
testcase_79 | AC | 662 ms
160,528 KB |
testcase_80 | AC | 577 ms
159,676 KB |
testcase_81 | AC | 620 ms
156,216 KB |
testcase_82 | AC | 551 ms
156,812 KB |
testcase_83 | AC | 360 ms
114,184 KB |
testcase_84 | AC | 305 ms
113,652 KB |
testcase_85 | AC | 652 ms
157,008 KB |
testcase_86 | AC | 628 ms
155,972 KB |
testcase_87 | AC | 382 ms
155,572 KB |
testcase_88 | AC | 370 ms
158,984 KB |
testcase_89 | RE | - |
testcase_90 | AC | 163 ms
80,308 KB |
testcase_91 | RE | - |
ソースコード
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)