#749638 (PyPy3) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	vwxyz
提出日時	2022-03-30 08:18:38
言語	PyPy3 (7.3.15)
結果	AC
実行時間	324 ms / 3,000 ms
コード長	5,669 bytes
コンパイル時間	420 ms
コンパイル使用メモリ	82,340 KB
実行使用メモリ	85,188 KB
最終ジャッジ日時	2024-11-14 05:56:45
合計ジャッジ時間	7,484 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	41 ms 54,532 KB
testcase_01	AC	41 ms 55,156 KB
testcase_02	AC	41 ms 53,712 KB
testcase_03	AC	106 ms 76,184 KB
testcase_04	AC	237 ms 84,840 KB
testcase_05	AC	147 ms 82,824 KB
testcase_06	AC	152 ms 81,904 KB
testcase_07	AC	40 ms 54,036 KB
testcase_08	AC	41 ms 55,268 KB
testcase_09	AC	40 ms 54,732 KB
testcase_10	AC	41 ms 53,972 KB
testcase_11	AC	41 ms 54,120 KB
testcase_12	AC	191 ms 80,316 KB
testcase_13	AC	171 ms 80,596 KB
testcase_14	AC	175 ms 80,372 KB
testcase_15	AC	249 ms 81,208 KB
testcase_16	AC	209 ms 79,768 KB
testcase_17	AC	247 ms 80,356 KB
testcase_18	AC	256 ms 80,608 KB
testcase_19	AC	260 ms 81,436 KB
testcase_20	AC	275 ms 81,808 KB
testcase_21	AC	285 ms 83,052 KB
testcase_22	AC	288 ms 83,860 KB
testcase_23	AC	296 ms 83,380 KB
testcase_24	AC	298 ms 83,676 KB
testcase_25	AC	318 ms 84,856 KB
testcase_26	AC	324 ms 85,188 KB
testcase_27	AC	54 ms 62,224 KB
testcase_28	AC	54 ms 64,180 KB
testcase_29	AC	58 ms 64,748 KB
testcase_30	AC	202 ms 81,076 KB
testcase_31	AC	233 ms 79,784 KB
testcase_32	AC	41 ms 53,636 KB
testcase_33	AC	41 ms 55,532 KB
testcase_34	AC	41 ms 54,716 KB
testcase_35	AC	41 ms 55,168 KB

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

ソースコード

raw source code

import heapq
import sys
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
readline=sys.stdin.readline

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
        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)
        if self.label:
            self.labelR=self.f(self.labelR,x)

    def heappop(self):
        x=heappop(self.queueR)
        if self.label:
            self.labelR=self.f_inve(self.labelR,x)
        return x

    def heappushpop(self,x):
        y=heappushpop(self.queueR,x)
        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)
        if self.label:
            self.labelL=self.f(self.labelL,x)

    def _heappop_max(self):
        x=_heappop_max(self.queueL)
        if self.label:
            self.labelL=self.f_inve(self.labelL,x)
        return x

    def _heappushpop_max(self,x):
        y=_heappushpop_max(self.queueL,x)
        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):
        self._heappush_max(self.heappushpop(x))

    def Push_Right(self,x):
        self.heappush(self._heappushpop_max(x))

    def Pop_Left(self):
        if self.queueL:
            retu=self._heappop_max()
        else:
            retu=None
        return retu

    def Pop_Right(self):
        if self.queueR:
            retu=self.heappop()
        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 __len__(self):
        retu=len(self.queueL)+len(self.queueR)
        if self.median and self.median_value!=None:
            retu+=1
        return retu

    def __str__(self):
        if self.median:
            if self.median_value==None:
                return "["+", ".join(map(str,sorted(self.queueL)))+"]+["+", ".join(map(str,sorted(self.queueR)))+"]"
            else:
                return "["+", ".join(map(str,sorted(self.queueL)))+"]+"+str(self.median_value)+"+["+", ".join(map(str,sorted(self.queueR)))+"]"
        else:
            return "["+", ".join(map(str,sorted(self.queueL)))+"]+["+", ".join(map(str,sorted(self.queueR)))+"]"

Q,K=map(int,readline().split())
ST=Slope_Trick()
for _ in range(Q):
    data=map(int,readline().split())
    q=next(data)
    if q==1:
        v=next(data)
        if len(ST.queueL)<K:
            ST.Push_Left(v)
        else:
            ST.Push_Right(v)
    else:
        if len(ST.queueL)==K:
            ans=ST.Pop_Left()
            if ST.queueR:
                ST.Push_Left(ST.Pop_Right())
        else:
            ans=-1
        print(ans)

yukicoder

結果

テストケース

ソースコード