結果
問題 | No.738 平らな農地 |
ユーザー | terasa |
提出日時 | 2023-01-09 00:45:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,067 ms / 2,000 ms |
コード長 | 8,134 bytes |
コンパイル時間 | 772 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 155,672 KB |
最終ジャッジ日時 | 2024-05-09 14:28:13 |
合計ジャッジ時間 | 44,529 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 83 ms
69,376 KB |
testcase_01 | AC | 83 ms
69,504 KB |
testcase_02 | AC | 80 ms
68,992 KB |
testcase_03 | AC | 80 ms
69,120 KB |
testcase_04 | AC | 79 ms
69,504 KB |
testcase_05 | AC | 199 ms
81,024 KB |
testcase_06 | AC | 199 ms
81,152 KB |
testcase_07 | AC | 184 ms
81,280 KB |
testcase_08 | AC | 151 ms
79,104 KB |
testcase_09 | AC | 131 ms
78,848 KB |
testcase_10 | AC | 114 ms
78,976 KB |
testcase_11 | AC | 155 ms
79,360 KB |
testcase_12 | AC | 130 ms
78,080 KB |
testcase_13 | AC | 197 ms
80,768 KB |
testcase_14 | AC | 135 ms
77,952 KB |
testcase_15 | AC | 611 ms
146,816 KB |
testcase_16 | AC | 634 ms
149,504 KB |
testcase_17 | AC | 672 ms
148,736 KB |
testcase_18 | AC | 658 ms
147,328 KB |
testcase_19 | AC | 752 ms
155,648 KB |
testcase_20 | AC | 631 ms
149,504 KB |
testcase_21 | AC | 692 ms
155,008 KB |
testcase_22 | AC | 652 ms
150,784 KB |
testcase_23 | AC | 695 ms
153,472 KB |
testcase_24 | AC | 701 ms
151,168 KB |
testcase_25 | AC | 134 ms
78,464 KB |
testcase_26 | AC | 135 ms
79,232 KB |
testcase_27 | AC | 136 ms
79,104 KB |
testcase_28 | AC | 131 ms
79,360 KB |
testcase_29 | AC | 130 ms
78,848 KB |
testcase_30 | AC | 132 ms
79,232 KB |
testcase_31 | AC | 133 ms
78,464 KB |
testcase_32 | AC | 131 ms
79,360 KB |
testcase_33 | AC | 134 ms
79,232 KB |
testcase_34 | AC | 131 ms
79,488 KB |
testcase_35 | AC | 129 ms
78,848 KB |
testcase_36 | AC | 133 ms
79,488 KB |
testcase_37 | AC | 129 ms
79,360 KB |
testcase_38 | AC | 134 ms
79,232 KB |
testcase_39 | AC | 133 ms
79,104 KB |
testcase_40 | AC | 133 ms
78,080 KB |
testcase_41 | AC | 135 ms
79,360 KB |
testcase_42 | AC | 128 ms
79,104 KB |
testcase_43 | AC | 130 ms
78,464 KB |
testcase_44 | AC | 135 ms
79,488 KB |
testcase_45 | AC | 670 ms
154,368 KB |
testcase_46 | AC | 650 ms
149,120 KB |
testcase_47 | AC | 661 ms
152,832 KB |
testcase_48 | AC | 625 ms
151,424 KB |
testcase_49 | AC | 620 ms
150,144 KB |
testcase_50 | AC | 629 ms
152,960 KB |
testcase_51 | AC | 671 ms
153,600 KB |
testcase_52 | AC | 631 ms
151,552 KB |
testcase_53 | AC | 642 ms
151,680 KB |
testcase_54 | AC | 667 ms
153,472 KB |
testcase_55 | AC | 673 ms
153,472 KB |
testcase_56 | AC | 665 ms
152,704 KB |
testcase_57 | AC | 619 ms
146,432 KB |
testcase_58 | AC | 643 ms
153,216 KB |
testcase_59 | AC | 652 ms
154,880 KB |
testcase_60 | AC | 658 ms
154,368 KB |
testcase_61 | AC | 647 ms
153,984 KB |
testcase_62 | AC | 617 ms
149,632 KB |
testcase_63 | AC | 711 ms
155,136 KB |
testcase_64 | AC | 663 ms
154,624 KB |
testcase_65 | AC | 850 ms
149,120 KB |
testcase_66 | AC | 872 ms
154,368 KB |
testcase_67 | AC | 606 ms
152,280 KB |
testcase_68 | AC | 604 ms
154,436 KB |
testcase_69 | AC | 755 ms
154,388 KB |
testcase_70 | AC | 683 ms
155,672 KB |
testcase_71 | AC | 305 ms
103,680 KB |
testcase_72 | AC | 290 ms
106,752 KB |
testcase_73 | AC | 274 ms
107,136 KB |
testcase_74 | AC | 309 ms
111,104 KB |
testcase_75 | AC | 751 ms
150,908 KB |
testcase_76 | AC | 664 ms
153,916 KB |
testcase_77 | AC | 761 ms
149,456 KB |
testcase_78 | AC | 802 ms
154,948 KB |
testcase_79 | AC | 813 ms
155,204 KB |
testcase_80 | AC | 690 ms
154,256 KB |
testcase_81 | AC | 744 ms
152,840 KB |
testcase_82 | AC | 760 ms
154,680 KB |
testcase_83 | AC | 359 ms
102,144 KB |
testcase_84 | AC | 332 ms
102,272 KB |
testcase_85 | AC | 1,067 ms
154,212 KB |
testcase_86 | AC | 976 ms
150,872 KB |
testcase_87 | AC | 580 ms
154,476 KB |
testcase_88 | AC | 535 ms
151,804 KB |
testcase_89 | AC | 84 ms
68,992 KB |
testcase_90 | AC | 81 ms
69,760 KB |
testcase_91 | AC | 82 ms
69,632 KB |
ソースコード
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))