結果

問題 No.649 ここでちょっとQK！
ユーザー titan23titan23
提出日時 2022-10-20 01:18:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 8,461 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 87,016 KB
実行使用メモリ 133,248 KB
最終ジャッジ日時 2023-09-12 12:18:26
合計ジャッジ時間 16,762 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 73 ms
71,592 KB
testcase_02 WA -
testcase_03 AC 202 ms
98,408 KB
testcase_04 AC 1,033 ms
130,972 KB
testcase_05 AC 1,054 ms
133,248 KB
testcase_06 WA -
testcase_07 AC 74 ms
71,544 KB
testcase_08 AC 73 ms
71,636 KB
testcase_09 AC 74 ms
71,376 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 406 ms
99,608 KB
testcase_13 AC 380 ms
97,872 KB
testcase_14 AC 389 ms
96,344 KB
testcase_15 AC 386 ms
97,496 KB
testcase_16 AC 382 ms
98,544 KB
testcase_17 AC 437 ms
100,336 KB
testcase_18 AC 480 ms
102,284 KB
testcase_19 AC 479 ms
104,500 KB
testcase_20 AC 537 ms
107,820 KB
testcase_21 AC 531 ms
108,028 KB
testcase_22 AC 615 ms
110,512 KB
testcase_23 AC 555 ms
111,920 KB
testcase_24 AC 631 ms
112,848 KB
testcase_25 AC 634 ms
116,040 KB
testcase_26 AC 675 ms
117,840 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 73 ms
71,572 KB
testcase_35 AC 74 ms
71,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
0