結果

問題 No.738 平らな農地
ユーザー ああいい
提出日時 2022-03-11 18:12:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 342 ms / 2,000 ms
コード長 1,616 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 123,904 KB
最終ジャッジ日時 2024-09-15 21:35:25
合計ジャッジ時間 19,799 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#BIT plus ver
class BITplus:
def __init__(self,N):
self.N = N
self.bit = [0] * (self.N+1)
def add(self,i,x):
while i <= self.N:
self.bit[i] += x
i += i & -i
def fold(self,i):
ans = 0
while i > 0:
ans += self.bit[i]
i -= i & -i
return ans
def lb(self,w):
if w <= 0:return 0
x = 0
k = 1
while k <= self.N:
k <<= 1
k >>= 1
while k:
if x + k <= self.N and self.bit[x+k] < w:
w -= self.bit[x+k]
x += k
k >>= 1
return x + 1
# N
def build(self,seq):
bit = self.bit
N = self.N
for i in range(N):
bit[i+1] = seq[i]
for i in range(1,N+1):
if i + (i & -1) <= N:
bit[i + (i & -i)] += bit[i]
N,K = map(int,input().split())
A = list(map(int,input().split()))
rD = sorted(set(A))
D = {v:i for i,v in enumerate(rD)}
n = len(D)
bit1 = BITplus(n)
bit2 = BITplus(n)
mid = (K+1) // 2
for i in range(K):
a = A[i]
bit1.add(D[a]+1,1)
bit2.add(D[a]+1,a)
ans = 10 ** 18
for i in range(K-1,N):
if i >= K:
a = A[i]
b = A[i-K]
bit1.add(D[a]+1,1)
bit2.add(D[a]+1,a)
bit1.add(D[b]+1,-1)
bit2.add(D[b]+1,-b)
m = bit1.lb(mid)
mm = bit1.fold(m)
t1 = bit2.fold(m)
t2 = bit2.fold(n) - t1
tmp = rD[m-1] * mm - t1 + t2 - rD[m-1] * (K - mm)
if tmp < ans:
ans = tmp
#print(m,mm,t1,t2,tmp)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0