結果

問題 No.2304 Distinct Elements
ユーザー vwxyz
提出日時 2023-06-06 19:32:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,265 ms / 3,000 ms
コード長 6,837 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 13,440 KB
実行使用メモリ 33,240 KB
最終ジャッジ日時 2024-12-29 08:42:06
合計ジャッジ時間 40,153 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

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

import sys
readline=sys.stdin.readline
import heapq
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
if heap and item < heap[0]:
item, heap[0] = heap[0], item
heapq._siftup_max(heap, 0)
return item
class Slope_Trick:
def __init__(self,L=False,R=False,median=False,label=False,f=None,f_inve=None,e=None):
self.queueL=[]
self.queueR=[]
self.L=L
self.R=R
self.median=median
if self.median:
self.median_value=None
self.label=label
self.shiftL=0
self.shiftR=0
self.min_f=0
if self.label:
self.f=f
self.f_inve=f_inve
self.e=e
self.labelL=self.e
self.labelR=self.e
def heappush(self,x):
heappush(self.queueR,x-self.shiftR)
if self.label:
self.labelR=self.f(self.labelR,x)
def heappop(self):
x=heappop(self.queueR)+self.shiftR
if self.label:
self.labelR=self.f_inve(self.labelR,x)
return x
def heappushpop(self,x):
y=heappushpop(self.queueR,x-self.shiftR)+self.shiftR
if self.label:
self.labelR=self.f(self.labelR,x)
self.labelR=self.f_inve(self.labelR,y)
return y
def _heappush_max(self,x):
_heappush_max(self.queueL,x-self.shiftL)
if self.label:
self.labelL=self.f(self.labelL,x)
def _heappop_max(self):
x=_heappop_max(self.queueL)+self.shiftL
if self.label:
self.labelL=self.f_inve(self.labelL,x)
return x
def _heappushpop_max(self,x):
y=_heappushpop_max(self.queueL,x-self.shiftL)+self.shiftL
if self.label:
self.labelL=self.f(self.labelL,x)
self.labelL=self.f_inve(self.labelL,y)
return y
def push_Left(self,x):
if self.queueR:
self.min_f+=max(x-(self.queueR[0]+self.shiftR),0)
self._heappush_max(self.heappushpop(x))
def push_Right(self,x):
if self.queueL:
self.min_f+=max((self.queueL[0]+self.shiftL)-x,0)
self.heappush(self._heappushpop_max(x))
def pop_Left(self):
if self.queueL:
retu=self._heappop_max()
if self.queueR:
self.min_f+=max(retu-(self.queueR[0]+self.shiftR),0)
else:
retu=None
return retu
def pop_Right(self):
if self.queueR:
retu=self.heappop()
if self.queueL:
self.min_f+=max((self.queueL[0]+self.shiftL)-retu,0)
else:
retu=None
return retu
def push(self,x):
if self.L:
if len(self.queueL)<self.L:
self.push_Left(x)
else:
self.push_Right(x)
if self.R:
if len(self.queueR)<self.R:
self.push_Right(x)
else:
self.push_Left(x)
if self.median:
if self.median_value==None:
if self.queueL and x<self.queueL[0]:
self.median_value=self._heappushpop_max(x)
elif self.queueR and self.queueR[0]<x:
self.median_value=self.heappushpop(x)
else:
self.median_value=x
else:
if self.median_value<=x:
self._heappush_max(self.median_value)
self.heappush(x)
else:
self._heappush_max(x)
self.heappush(self.median_value)
self.median_value=None
def pop(self):
if self.L:
if len(self.queueL)==self.L:
retu=self._heappop_max()
if self.queueR:
self._heappush_max(self.heappop())
else:
retu=None
if self.R:
if len(self.queueR)==self.R:
retu=self.heappop()
if self.queueL:
self.heappush(self._heappop_max())
else:
retu=None
if self.median:
if self.median_value==None:
retu=(self.pop_Left(),self.pop_Right())
else:
retu=(self.median_value,None)
self.median_value=None
return retu
def top(self):
if self.L:
if len(self.queueL)==self.L:
retu=self.queueL[0]
else:
retu=None
if self.R:
if len(self.queueR)==self.R:
retu=self.queueR[0]
else:
retu=None
if self.median:
if self.median_value==None:
if self.queueL:
retu=(self.queueL[0],self.queueR[0])
else:
retu=(None,None)
else:
retu=(self.median_value,None)
return retu
def top_Left(self):
if self.queueL:
return self.queueL[0]+self.shiftL
else:
return None
def top_Right(self):
if self.queueR:
return self.queueR[0]+self.shiftR
else:
return None
def Shift_Left(self,a):
self.shiftL+=a
def Shift_Right(self,a):
self.shiftR+=a
def Label_Left(self):
return self.labelL
def Label_Right(self):
return self.labelR
def Cumultive_min(self):
self.queueR=[]
def Cumultive_max(self):
self.queueL=[]
def __len__(self):
retu=len(self.queueL)+len(self.queueR)
if self.median and self.median_value!=None:
retu+=1
return retu
def __call__(self,x):
return sum(max((l+self.shiftL)-x,0) for l in self.queueL)+sum(max(x-(r+self.shiftR),0) for r in self.queueR)+self.min_f
def __str__(self):
if self.median:
if self.median_value==None:
return "["+", ".join(map(str,sorted([x+self.shiftL for x in self.queueL])))+"]+["+", ".join(map(str,sorted([x+self.shiftR for x in
                    self.queueR])))+"]"
else:
return "["+", ".join(map(str,sorted([x+self.shiftL for x in self.queueL])))+"]+"+str(self.median_value)+"+["+", ".join(map(str,sorted
                    ([x+self.shiftR for x in self.queueR])))+"]"
else:
return "["+", ".join(map(str,sorted([x+self.shiftL for x in self.queueL])))+"]+["+", ".join(map(str,sorted([x+self.shiftR for x in self
                .queueR])))+"]"
N=int(readline())
A=sorted(list(map(int,readline().split())))
ST=Slope_Trick()
for a in A:
ST.Cumultive_min()
ST.Shift_Left(1)
ST.push_Right(a)
ST.push_Left(a)
ans=ST.min_f
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0