#878462 (Python3) No.2304 Distinct Elements

提出ソース

結果

問題	No.2304 Distinct Elements
ユーザー	vwxyz
提出日時	2023-06-06 19:32:00
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,035 ms / 3,000 ms
コード長	6,837 bytes
コンパイル時間	86 ms
コンパイル使用メモリ	11,428 KB
実行使用メモリ	30,860 KB
最終ジャッジ日時	2023-08-28 10:46:23
合計ジャッジ時間	33,151 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	18 ms 8,908 KB
testcase_01	AC	18 ms 8,912 KB
testcase_02	AC	19 ms 8,852 KB
testcase_03	AC	22 ms 8,792 KB
testcase_04	AC	980 ms 24,036 KB
testcase_05	AC	989 ms 24,076 KB
testcase_06	AC	985 ms 24,124 KB
testcase_07	AC	988 ms 24,108 KB
testcase_08	AC	974 ms 23,996 KB
testcase_09	AC	856 ms 30,720 KB
testcase_10	AC	846 ms 30,824 KB
testcase_11	AC	861 ms 30,652 KB
testcase_12	AC	861 ms 30,808 KB
testcase_13	AC	855 ms 30,728 KB
testcase_14	AC	20 ms 8,884 KB
testcase_15	AC	19 ms 8,800 KB
testcase_16	AC	20 ms 8,828 KB
testcase_17	AC	19 ms 8,820 KB
testcase_18	AC	19 ms 8,916 KB
testcase_19	AC	18 ms 8,952 KB
testcase_20	AC	18 ms 8,948 KB
testcase_21	AC	19 ms 8,792 KB
testcase_22	AC	18 ms 8,856 KB
testcase_23	AC	19 ms 8,952 KB
testcase_24	AC	19 ms 8,920 KB
testcase_25	AC	18 ms 8,864 KB
testcase_26	AC	19 ms 8,960 KB
testcase_27	AC	18 ms 8,896 KB
testcase_28	AC	19 ms 8,772 KB
testcase_29	AC	747 ms 25,116 KB
testcase_30	AC	68 ms 10,504 KB
testcase_31	AC	602 ms 22,280 KB
testcase_32	AC	664 ms 25,848 KB
testcase_33	AC	64 ms 10,672 KB
testcase_34	AC	690 ms 26,360 KB
testcase_35	AC	768 ms 28,448 KB
testcase_36	AC	55 ms 10,012 KB
testcase_37	AC	300 ms 15,196 KB
testcase_38	AC	1,017 ms 29,332 KB
testcase_39	AC	1,035 ms 29,596 KB
testcase_40	AC	637 ms 14,772 KB
testcase_41	AC	325 ms 11,824 KB
testcase_42	AC	958 ms 18,188 KB
testcase_43	AC	995 ms 30,860 KB
testcase_44	AC	601 ms 24,324 KB
testcase_45	AC	532 ms 22,292 KB
testcase_46	AC	399 ms 18,560 KB
testcase_47	AC	20 ms 8,936 KB
testcase_48	AC	19 ms 8,816 KB
testcase_49	AC	1,007 ms 30,788 KB
testcase_50	AC	1,000 ms 30,816 KB
testcase_51	AC	1,001 ms 30,724 KB
testcase_52	AC	999 ms 21,268 KB
testcase_53	AC	590 ms 30,648 KB
testcase_54	AC	969 ms 19,524 KB
testcase_55	AC	964 ms 18,836 KB
testcase_56	AC	954 ms 18,524 KB
testcase_57	AC	1,001 ms 30,724 KB
testcase_58	AC	993 ms 30,772 KB
testcase_59	AC	990 ms 19,676 KB
testcase_60	AC	18 ms 8,760 KB
testcase_61	AC	17 ms 8,912 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード