結果

問題 No.3298 K-th Slime
コンテスト
ユーザー tkykwtnb
提出日時 2026-01-04 20:04:19
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 4,686 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 281 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 98,832 KB
最終ジャッジ日時 2026-01-04 20:04:28
合計ジャッジ時間 8,455 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')
class SortedList(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170
    def _build(self, a: Optional[List[T]] = None) -> None:
        "Evenly divide `a` into buckets."
        if a is None:a=list(self)
        size=len(a)
        bucket_size=int(math.ceil(math.sqrt(size/self.BUCKET_RATIO)))
        self.a=[a[size*i//bucket_size:size*(i+1)//bucket_size] for i in range(bucket_size)]
    def __init__(self,a:Iterable[T]=[])->None:
        "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
        a=list(a)
        self.size=len(a)
        if not all(a[i]<a[i+1] for i in range(len(a)-1)):
            a=sorted(list(a))
        self._build(a)
    def __iter__(self)->Iterator[T]:
        for i in self.a:
            for j in i:yield j
    def __reversed__(self)->Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i):yield j
    def __eq__(self, other)->bool:
        return list(self)==list(other)
    def __len__(self)->int:
        return self.size
    def __repr__(self)->str:
        return "SortedSet"+str(self.a)
    def __str__(self)->str:
        s = str(list(self))
        return "{"+s[1:len(s)-1]+"}"
    def _position(self,x:T)->Tuple[List[T],int]:
        "Find the bucket and position which x should be inserted. self must not be empty."
        for a in self.a:
            if x<=a[-1]: break
        return (a,bisect_left(a,x))
    def __contains__(self,x:T)->bool:
        if self.size==0:return False
        a,i=self._position(x)
        return i!=len(a) and a[i]==x
    def __getitem__(self,i:int)->T:
        "Return the i-th element."
        if i<0:
            for a in reversed(self.a):
                i+=len(a)
                if i>=0:return a[i]
        else:
            for a in self.a:
                if i<len(a):return a[i]
                i-=len(a)
        raise IndexError
    def _pop(self,a:List[T],i:int)->T:
        ans=a.pop(i)
        self.size-=1
        if not a:self._build()
        return ans
    def add(self,x:T)->bool:
        "Add an element and return True if added. / O(√N)"
        if self.size==0:
            self.a=[[x]]
            self.size=1
            return True
        a,i=self._position(x)
        if i!=len(a) and a[i]==x:return False
        a.insert(i,x)
        self.size+=1
        if len(a)>len(self.a)*self.REBUILD_RATIO:
            self._build()
        return True
    def discard(self,x:T)->bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size==0:return False
        a,i=self._position(x)
        if i==len(a) or a[i]!=x:return False
        self._pop(a,i)
        return True
    def pop(self,i:int=-1)->T:
        "Pop and return the i-th element."
        if i<0:
            for a in reversed(self.a):
                i+=len(a)
                if i>=0:return self._pop(a,i)
        else:
            for a in self.a:
                if i<len(a):return self._pop(a,i)
                i-=len(a)
        raise IndexError
    def index(self,x:T)->int:
        "Count the number of elements < x."
        ans=0
        for a in self.a:
            if a[-1]>=x:
                return ans+bisect_left(a,x)
            ans+=len(a)
        return ans
    def index_right(self,x:T)->int:
        "Count the number of elements <= x."
        ans=0
        for a in self.a:
            if a[-1]>x:
                return ans+bisect_right(a,x)
            ans+=len(a)
        return ans
    def lt(self,x:T)->Optional[T]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0]<x:
                return a[bisect_left(a,x)-1]
    def le(self,x:T)->Optional[T]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0]<=x:
                return a[bisect_right(a,x)-1]
    def gt(self,x:T)->Optional[T]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1]>x:
                return a[bisect_right(a,x)]
    def ge(self,x:T)->Optional[T]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1]>=x:
                return a[bisect_left(a,x)]
N,K,Q=map(int,input().split())
A=SortedList(map(int,input().split()))
for _ in range(Q):
    q=list(map(int,input().split()))
    if q[0]==1:
        A.add(q[1])
    elif q[0]==2:
        s=A.pop(K-1)
        A.add(s+q[1])
    else:
        print(A[K-1])
0