• [1536] The Kth Lightest

  • 时间限制: 2000 ms 内存限制: 65535 K
  • 问题描述
  • Have you played the can tower? Put the cans one by one on the can tower lead to much happiness to me. Today I will play the can tower again. I will play 3 kinds of operations as followed.
    1. Put w: I will put a new can on the top of the can tower and w is the weight of the current can. Note that at the beginning the can tower has 0 cans.
    2. Take: I will take away the top can of the can tower.
    3. Query: I want to know the kth lightest can’s weight in the current can tower. Note that the k is given at the beginning of the game.
  • 输入
  • On the first line there is a single integer T meaning the number of test cases. Then there are T test cases.
    In each test case on the first line there are two integers n (0 < n < 10^5) and k (0 < k< 10^9). n means the number of operations and k means that you should output the kth lightest can's weight. Following there are n operations each one line.
    The operation is either“Put w”or“Take”or“Query”. Note that operations will not be illegal. That means if there are no cans in the can tower , I will never play“Take”and“Query” operations. All the weights are not necessary unique.
  • 输出
  • For each“Take”operation , please output the top can's weight before being taken away.
    For each“Query”operation , please output the kth lightest can's weight. If the number of cans in can tower is smaller than the k , please output the heavest can's weight in the current can tower.
  • 样例输入
  • 1
    10 3
    Put 3
    Put 1
    Put 2
    Put 6
    Put 3
  • 样例输出
  • 3
  • 提示
  • 来源
  • zzxchavo@HEU
  • 操作