ALLIN1 - All in One


Before you begin, you should try this problem! AVL Tree

This problem is simple. Initially, there is a list and it's empty. Then you are given four types of query.

  1. Insert data to the list
  2. Remove data from the list
  3. Print an index (1-based) from a specified data after the list was sorted ascendingly
  4. Print data from a specified index (1-based) after the list was sorted ascendingly

Input

Input contains several lines. Each line follows one of these formats.
1 n: Insert n (0 <= n <= 231 - 1) to the list
2 n: Remove n from the list. If n was not found, do nothing
3 n: Print n's index (1-based) after the list was sorted ascendingly
4 i: Print data on i-th index (1-based) after the list was sorted ascendingly (0 <= i <= 231 - 1)
-1: End of input

Output

For each query 3, print n's index in one line. If n was not found, just print -1
For each query 4, print data on i-th index in one line. If the index is not valid, just print -1

Example

Input:
3 20
-1 Output: -1
 

hide comments
changyouren: 2021-10-03 13:27:01

scanf is too slow , you should use fread.
treap is correct method

andy489: 2021-09-09 19:48:34

"Time limit was set carefully to only accept well-designed solution." Well what's wrong with the Treap design with Nodes storing count of subtrees and frequency of current key???

andy489: 2021-09-09 19:38:47

I am also searchng for a Treap solution. I am getting TLE, but all my queries are log(n). Can anyone share?

adventurersali: 2020-04-14 20:35:29

Had anyone solved this problem using Treap, it time limits on me.

zer0_h6cks: 2019-12-03 07:41:41

Can someone help? I'm using splay trees which should be log n amortized but getting TLE.

nitesh_gupta: 2019-09-30 11:55:57

For 4th query, you have to print -1 if i (given as input) is 0.

akjol2049: 2018-11-25 10:51:33

do all elements will be distinct?

hrishabh: 2017-05-09 12:59:44

Can anyone help i am getting time limit exceed, all operations answered in O(1) but still :( .

Re: They are not O(1).

Last edit: 2017-05-16 17:09:28
pandey01: 2017-04-25 13:50:37

Anyone pro here? i need some help...

pvsmpraveen: 2017-04-24 17:01:05

Thank you MIN_25, that helped me!

Finally AC :)

Last edit: 2017-04-24 17:01:17

Added by:Lucas
Date:2017-04-22
Time limit:1s-1.350s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All