結果
問題 | No.2304 Distinct Elements |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysreadline=sys.stdin.readlineimport heapqfrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _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], itemheapq._siftup_max(heap, 0)return itemclass 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=Lself.R=Rself.median=medianif self.median:self.median_value=Noneself.label=labelself.shiftL=0self.shiftR=0self.min_f=0if self.label:self.f=fself.f_inve=f_inveself.e=eself.labelL=self.eself.labelR=self.edef 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.shiftRif self.label:self.labelR=self.f_inve(self.labelR,x)return xdef heappushpop(self,x):y=heappushpop(self.queueR,x-self.shiftR)+self.shiftRif self.label:self.labelR=self.f(self.labelR,x)self.labelR=self.f_inve(self.labelR,y)return ydef _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.shiftLif self.label:self.labelL=self.f_inve(self.labelL,x)return xdef _heappushpop_max(self,x):y=_heappushpop_max(self.queueL,x-self.shiftL)+self.shiftLif self.label:self.labelL=self.f(self.labelL,x)self.labelL=self.f_inve(self.labelL,y)return ydef 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=Nonereturn retudef 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=Nonereturn retudef 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=xelse: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=Nonedef 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=Noneif self.R:if len(self.queueR)==self.R:retu=self.heappop()if self.queueL:self.heappush(self._heappop_max())else:retu=Noneif self.median:if self.median_value==None:retu=(self.pop_Left(),self.pop_Right())else:retu=(self.median_value,None)self.median_value=Nonereturn retudef top(self):if self.L:if len(self.queueL)==self.L:retu=self.queueL[0]else:retu=Noneif self.R:if len(self.queueR)==self.R:retu=self.queueR[0]else:retu=Noneif 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 retudef top_Left(self):if self.queueL:return self.queueL[0]+self.shiftLelse:return Nonedef top_Right(self):if self.queueR:return self.queueR[0]+self.shiftRelse:return Nonedef Shift_Left(self,a):self.shiftL+=adef Shift_Right(self,a):self.shiftR+=adef Label_Left(self):return self.labelLdef Label_Right(self):return self.labelRdef 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+=1return retudef __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_fdef __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 inself.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_fprint(ans)