結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー るさ
提出日時 2020-12-22 15:04:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,078 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 92,312 KB
最終ジャッジ日時 2024-09-21 14:11:32
合計ジャッジ時間 7,071 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 4 WA * 1 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Order_Set:
    def __init__(self, deep:int):
        self.deep = deep
        self.length = 2 ** (deep+1) -1
        self.value = [0] * self.length
        self.used = [False] * self.length
        self.free = [0] * self.length
        self.capacity = [0] * self.length
        for i in range(2 ** deep -1, self.length):
            self.free[i] = 1
            self.capacity[i] = 1

        for i in range(2 ** deep -2, -1, -1):
            self.free[i] = self.free[2*i+1] + self.free[2*i+2] + 1
            self.capacity[i] = self.free[i]

    def insert(self, value:int, x=0, min_over=True):
        f = (False,)
        if self.free[x] == 0:
            if min_over:
                m = self.min_pop(x)
                f = (True, min(value, m))
                value = max(value, m)
            else:
                m = self.max_pop(x)
                f = (True, max(value, m))
                value = min(value, m)

        if not self.used[x]:
            self.used[x] = True
            self.value[x] = value
            t = x*2+1
            while t != 0:
                t = (t-1) // 2
                self.free[t] -= 1
            return f

        if value == self.value[x]:
            return f
        elif value > self.value[x]:
            r = self.insert(value, x*2+2, True)
            if r[0]:
                t = self.value[x]
                self.value[x] = r[1]
                self.insert(t, x*2+1)
            return f
        else:
            r = self.insert(value, x*2+1, False)
            if r[0]:
                t = self.value[x]
                self.value[x] = r[1]
                self.insert(t, x*2+2)
            return f

    def min_pop(self, x:int):
        if x*2+1 >= self.length:
            r = self.value[x]
            self.used[x] = False
            x = x*2+1
            while x != 0:
                x = (x-1) // 2
                self.free[x] += 1
            return r

        if self.used[x*2+1]:
            return self.min_pop(x*2+1)
        r = self.value[x]
        if self.used[x*2+2]:
            self.value[x] = self.min_pop(x*2+2)
        else:
            self.used[x] = False
            x = x*2+1
            while x != 0:
                x = (x-1) // 2
                self.free[x] += 1
        return r

    def max_pop(self, x:int):
        if x*2+1 >= self.length:
            r = self.value[x]
            self.used[x] = False
            x = x*2+1
            while x != 0:
                x = (x-1) // 2
                self.free[x] += 1
            return r

        if self.used[x*2+2]:
            return self.max_pop(x*2+2)
        r = self.value[x]
        if self.used[x*2+1]:
            self.value[x] = self.max_pop(x*2+1)
        else:
            self.used[x] = False
            x = x*2+1
            while x != 0:
                x = (x-1) // 2
                self.free[x] += 1
        return r

    def erase(self, value:int):
        x = 0
        while True:
            if x >= self.length or not self.used[x]:
                return
            if self.value[x] > value:
                x = x*2+1
            elif self.value[x] < value:
                x = x*2+2
            if self.value[x] == value:
                if x*2+1 < self.length:
                    le = not self.used[x*2+1]
                    re = not self.used[x*2+2]
                else:
                    le = True
                    re = True
                if le and re:
                    self.used[x] = False
                    x = x*2+1
                    while x != 0:
                        x = (x-1) // 2
                        self.free[x] += 1
                elif le:
                    self.value[x] = self.min_pop(x*2+2)
                else:
                    self.value[x] = self.max_pop(x*2+1)
                return

    def lower_bound(self, v:int, x=0):
        if x >= self.length or not self.used[x]:
            return None
        s = set([self.value[x]])
        ll = self.lower_bound(v, x*2+1)
        rl = self.lower_bound(v, x*2+1)
        if not ll is None:
            s.add(ll)
        if not rl is None:
            s.add(rl)
        return min(s)

    def isin(self, v:int):
        return lower_bound(v) == v

    def index(self, id:int, x=0):
        if x*2+1 >= self.length:
            if id == 0:
                return self.value[x]
            else:
                raise IndexError("set index out of range")
        if not self.used[x]:
            raise IndexError("set index out of range")
        lp = self.capacity[x*2+1] - self.free[x*2+1]
        if id == lp:
            return self.value[x]
        elif id < lp:
            return self.index(id, x*2+1)
        else:
            return self.index(id-lp-1, x*2+2)


q,k = map(int, input().split())
os = Order_Set(10)
for qi in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        os.insert((query[1], qi))
    else:
        if os.capacity[0] - os.free[0] >= k:
            r = os.index(k-1)
            print(r[0])
            os.erase(r)
        else:
            print(-1)
0