結果
| 問題 | No.738 平らな農地 |
| ユーザー |
 terasa
|
| 提出日時 | 2023-01-10 19:36:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 749 ms / 2,000 ms |
| コード長 | 10,960 bytes |
| コンパイル時間 | 250 ms |
| コンパイル使用メモリ | 87,116 KB |
| 実行使用メモリ | 160,536 KB |
| 最終ジャッジ日時 | 2023-08-23 10:18:16 |
| 合計ジャッジ時間 | 41,141 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 172 ms
80,432 KB |
| testcase_01 | AC | 169 ms
80,408 KB |
| testcase_02 | AC | 170 ms
80,548 KB |
| testcase_03 | AC | 168 ms
80,424 KB |
| testcase_04 | AC | 171 ms
80,544 KB |
| testcase_05 | AC | 253 ms
85,612 KB |
| testcase_06 | AC | 275 ms
85,440 KB |
| testcase_07 | AC | 268 ms
86,104 KB |
| testcase_08 | AC | 251 ms
84,392 KB |
| testcase_09 | AC | 230 ms
83,408 KB |
| testcase_10 | AC | 210 ms
83,084 KB |
| testcase_11 | AC | 241 ms
83,872 KB |
| testcase_12 | AC | 232 ms
83,128 KB |
| testcase_13 | AC | 264 ms
85,568 KB |
| testcase_14 | AC | 236 ms
83,572 KB |
| testcase_15 | AC | 558 ms
153,040 KB |
| testcase_16 | AC | 565 ms
154,424 KB |
| testcase_17 | AC | 590 ms
155,608 KB |
| testcase_18 | AC | 580 ms
154,380 KB |
| testcase_19 | AC | 623 ms
156,380 KB |
| testcase_20 | AC | 557 ms
156,888 KB |
| testcase_21 | AC | 611 ms
156,272 KB |
| testcase_22 | AC | 572 ms
154,352 KB |
| testcase_23 | AC | 607 ms
155,368 KB |
| testcase_24 | AC | 609 ms
157,640 KB |
| testcase_25 | AC | 214 ms
83,320 KB |
| testcase_26 | AC | 221 ms
83,784 KB |
| testcase_27 | AC | 222 ms
83,796 KB |
| testcase_28 | AC | 216 ms
83,872 KB |
| testcase_29 | AC | 218 ms
83,792 KB |
| testcase_30 | AC | 216 ms
83,696 KB |
| testcase_31 | AC | 217 ms
83,832 KB |
| testcase_32 | AC | 214 ms
83,728 KB |
| testcase_33 | AC | 222 ms
83,408 KB |
| testcase_34 | AC | 216 ms
83,536 KB |
| testcase_35 | AC | 217 ms
83,772 KB |
| testcase_36 | AC | 220 ms
83,676 KB |
| testcase_37 | AC | 218 ms
83,632 KB |
| testcase_38 | AC | 219 ms
83,816 KB |
| testcase_39 | AC | 217 ms
83,400 KB |
| testcase_40 | AC | 218 ms
83,692 KB |
| testcase_41 | AC | 214 ms
83,196 KB |
| testcase_42 | AC | 224 ms
83,552 KB |
| testcase_43 | AC | 219 ms
83,648 KB |
| testcase_44 | AC | 227 ms
83,572 KB |
| testcase_45 | AC | 559 ms
158,780 KB |
| testcase_46 | AC | 563 ms
155,908 KB |
| testcase_47 | AC | 562 ms
157,548 KB |
| testcase_48 | AC | 532 ms
156,332 KB |
| testcase_49 | AC | 532 ms
153,968 KB |
| testcase_50 | AC | 530 ms
157,636 KB |
| testcase_51 | AC | 570 ms
156,760 KB |
| testcase_52 | AC | 543 ms
154,200 KB |
| testcase_53 | AC | 567 ms
158,892 KB |
| testcase_54 | AC | 586 ms
157,332 KB |
| testcase_55 | AC | 569 ms
157,056 KB |
| testcase_56 | AC | 570 ms
158,668 KB |
| testcase_57 | AC | 535 ms
154,288 KB |
| testcase_58 | AC | 541 ms
159,052 KB |
| testcase_59 | AC | 544 ms
158,820 KB |
| testcase_60 | AC | 543 ms
158,144 KB |
| testcase_61 | AC | 551 ms
157,584 KB |
| testcase_62 | AC | 523 ms
156,512 KB |
| testcase_63 | AC | 578 ms
158,532 KB |
| testcase_64 | AC | 557 ms
157,060 KB |
| testcase_65 | AC | 572 ms
156,352 KB |
| testcase_66 | AC | 593 ms
155,352 KB |
| testcase_67 | AC | 581 ms
154,648 KB |
| testcase_68 | AC | 581 ms
155,780 KB |
| testcase_69 | AC | 725 ms
159,580 KB |
| testcase_70 | AC | 643 ms
158,920 KB |
| testcase_71 | AC | 209 ms
102,448 KB |
| testcase_72 | AC | 211 ms
101,476 KB |
| testcase_73 | AC | 212 ms
104,008 KB |
| testcase_74 | AC | 211 ms
104,184 KB |
| testcase_75 | AC | 652 ms
155,040 KB |
| testcase_76 | AC | 611 ms
156,440 KB |
| testcase_77 | AC | 697 ms
151,184 KB |
| testcase_78 | AC | 749 ms
159,872 KB |
| testcase_79 | AC | 668 ms
160,536 KB |
| testcase_80 | AC | 587 ms
159,428 KB |
| testcase_81 | AC | 630 ms
156,144 KB |
| testcase_82 | AC | 569 ms
157,084 KB |
| testcase_83 | AC | 390 ms
114,408 KB |
| testcase_84 | AC | 324 ms
113,912 KB |
| testcase_85 | AC | 653 ms
156,932 KB |
| testcase_86 | AC | 631 ms
156,128 KB |
| testcase_87 | AC | 389 ms
155,684 KB |
| testcase_88 | AC | 374 ms
159,300 KB |
| testcase_89 | AC | 170 ms
80,416 KB |
| testcase_90 | AC | 169 ms
80,224 KB |
| testcase_91 | AC | 168 ms
80,568 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 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):
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)