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

• 問題: No.649 ここでちょっとQK！
• ユーザー: titan23
• 提出日時: 2022-10-20 01:18:55
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 8,461 bytes
• コンパイル時間: 249 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 130,184 KB
• 最終ジャッジ日時: 2024-06-30 00:42:29
• 合計ジャッジ時間: 13,435 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 2 WA * 2
other	AC * 22 WA * 10

ソースコード

import math
alpha = 0.75
beta = math.log2(1/alpha)


class ScapegoatTreeNode:
  # __slots__ = ('key', 'left', 'right', 'size')
  
  def __init__(self, key):
    self.key = key
    self.left = None
    self.right = None
    self.size = 1

  def __str__(self):
    if self.left is None and self.right is None:
      return f'key:{self.key, self.size}\n'
    return f'key:{self.key, self.size},\n left:{self.left},\n right:{self.right}\n'


class ScapegoatTreeSet:
 
  # __slots__ = ('node', '__iter', '__len')
 
  '''Make a new AVLTree. / O(NlogN)'''
  def __init__(self, a=[]) -> None:
    if a:
      aa = sorted(a)
      a = [aa[0]]
      for i in range(1, len(aa)):
        if aa[i] != a[-1]:
          a.append(aa[i])
    self.node = self.__build(a)
 
  def __build(self, a) -> None:
    def sort(l, r):
      if l >= r:
        return None, 0
      mid = (l + r) >> 1
      root = ScapegoatTreeNode(a[mid])
      root.left, sl = sort(l, mid)
      root.right, sr = sort(mid+1, r)
      root.size = sl + sr + 1
      return root, sl+sr+1
    return sort(0, len(a))[0]
 
  def __rebuild(self, node: ScapegoatTreeNode) -> ScapegoatTreeNode:
    a = []
    def get(node):
      if node.left is not None:
        get(node.left)
      a.append(node)
      if node.right is not None:
        get(node.right)
 
    def sort(l, r):
      if l >= r:
        return None, 0
      mid = (l + r) >> 1
      root = a[mid]
      root.left, sl = sort(l, mid)
      root.right, sr = sort(mid+1, r)
      root.size = sl + sr + 1
      return root, sl+sr+1
    get(node)
    return sort(0, len(a))[0]
 
  '''add a key. / O(logN)'''
  def add(self, key) -> bool:
    if self.node is None:
      self.node = ScapegoatTreeNode(key)
      return True
    node = self.node
    path, di = [], 0
    while node is not None:
      if key < node.key:
        path.append(node)
        di = di<<1 | 1
        node = node.left
      elif key > node.key:
        path.append(node)
        di = di<<1
        node = node.right
      else:
        return False
    if di & 1:
      path[-1].left = ScapegoatTreeNode(key)
    else:
      path[-1].right = ScapegoatTreeNode(key)
    if len(path)*beta > math.log(self.__len__()):
      node_size = 1
      while path:
        pnode = path.pop()
        di >>= 1
        pnode_size = pnode.size + 1
        if alpha * pnode_size < node_size:
          break
        node_size = pnode_size
      new_node = self.__rebuild(pnode)
      if not path:
        self.node = new_node
        return True
      if di & 1:
        path[-1].left = new_node
      else:
        path[-1].right = new_node
    for p in path:
      p.size += 1
    return True
 
  '''Discard key. / O(logN)'''
  def discard(self, key) -> bool:
    di = 1
    node = self.node
    path = []
    while node is not None:
      if key < node.key:
        path.append(node)
        di = 1
        node = node.left
      elif key > node.key:
        path.append(node)
        di = -1
        node = node.right
      else:
        break
    else:
      return False
    if node.left is not None and node.right is not None:
      path.append(node)
      di = 1
      lmax = node.left
      while lmax.right is not None:
        path.append(lmax)
        di = -1
        lmax = lmax.right
      node.key = lmax.key
      node = lmax
    cnode = node.right if node.left is None else node.left
    if path:
      if di == 1:
        path[-1].left = cnode
      else:
        path[-1].right = cnode
    else:
      self.node = cnode
    for p in path:
      p.size -= 1
    return True
 
  '''Find the largest element <= key, or None if it doesn't exist. / O(logN)'''
  def le(self, key):
    res, node = None, self.node
    while node is not None:
      if key < node.key:
        node = node.left
      elif key > node.key:
        res, node = node.key, node.right
      else:
        res = key
        break
    return res
 
  '''Find the largest element < key, or None if it doesn't exist. / O(logN)'''
  def lt(self, key):
    res, node = None, self.node
    while node is not None:
      if key < node.key:
        node = node.left
      elif key > node.key:
        res, node = node.key, node.right
      else:
        break
    return res
 
  '''Find the smallest element >= key, or None if it doesn't exist. / O(logN)'''
  def ge(self, key):
    res, node = None, self.node
    while node is not None:
      if key < node.key:
        res, node = node.key, node.left
      elif key > node.key:
        node = node.right
      else:
        res = key
        break
    return res
 
  '''Find the smallest element > key, or None if it doesn't exist. / O(logN)'''
  def gt(self, key):
    res, node = None, self.node
    while node is not None:
      if key < node.key:
        res, node = node.key, node.left
      elif key > node.key:
        node = node.right
      else:
        break
    return res
 
  '''Count the number of elements < key. / O(logN)'''
  def index(self, key) -> int:
    indx = 0
    node = self.node
    while node:
      if key < node.key:
        node = node.left
      elif key > node.key:
        indx += 1 if node.left is None else node.left.size + 1
        node = node.right
      else:
        indx += 0 if node.left is None else node.left.size
        break
    return indx

  '''Count the number of elements <= key. / O(logN)'''
  def index_right(self, key) -> int:
    indx = 0
    node = self.node
    while node:
      if key < node.key:
        node = node.left
      elif key > node.key:
        indx += 1 if node.left is None else node.left.size + 1
        node = node.right
      else:
        indx += 1 if node.left is None else node.left.size + 1
        break
    return indx

  '''Return and Remove max element or a[p]. / O(logN)'''
  def pop(self, p=-1):
    if p < 0:
      p += self.__len__()
    now = 0
    node = self.node
    path = []
    di = 1
    while node is not None:
      t = now if node.left is None else now + node.left.size
      if t < p:
        path.append(node)
        now = t + 1
        di = -1
        node = node.right
      elif t > p:
        path.append((node))
        di = 1
        node = node.left
      else:
        break
    else:
      raise IndexError(f'k={p}, len={self.__len__()}')
    res = node.key
    if node.left is not None and node.right is not None:
      path.append(node)
      di = 1
      lmax = node.left
      while lmax.right is not None:
        path.append(lmax)
        di = -1
        lmax = lmax.right
      node.key = lmax.key
      node = lmax
    cnode = node.right if node.left is None else node.left
    if path:
      if di == 1:
        path[-1].left = cnode
      else:
        path[-1].right = cnode
    else:
      self.node = cnode
    for p in path:
      p.size -= 1
    return res

  '''Return and Remove min element. / O(logN)'''
  def popleft(self):
    return self.pop(0)

  def __kth_elm(self, k):
    if k < 0:
      k += self.__len__()
    now, node = 0, self.node
    while node is not None:
      t = now if node.left is None else now + node.left.size
      if t < k:
        now, node = t + 1, node.right
      elif t > k:
        node = node.left
      else:
        return node.key
    raise IndexError(f'k={k}, len={self.__len__()}')

  def __contains__(self, x):
    node = self.node
    while node:
      if x < node.key:
        node = node.left
      elif x > node.key:
        node = node.right
      else:
        return True
    return False

  def __getitem__(self, x):
    return self.__kth_elm(x)

  def __iter__(self):
    self.__iter = 0
    return self

  def __next__(self):
    if self.__iter == self.__len__():
      raise StopIteration
    res = self.__getitem__(self.__iter)
    self.__iter += 1
    return res

  def __reversed__(self):
    for i in range(self.__len__()):
      yield self.__getitem__(-i-1)

  def __len__(self):
    return 0 if self.node is None else self.node.size

  def __bool__(self):
    return self.node is not None

  def __repr__(self):
    return '{' + ', '.join(map(str, self)) + '}'

  def __str__(self):
    return '{' + ', '.join(map(str, self)) + '}'



#  -----------------------  #

import sys
input = lambda: sys.stdin.readline().rstrip()

q, k = map(int, input().split())
avl = ScapegoatTreeSet()
query = [list(map(int, input().split())) for _ in range(q)]
for qu in query:
  if qu[0] == 1:
    avl.add(qu[1])
  else:
    if len(avl) < k:
      print(-1)
    else:
      print(avl.pop(k-1))