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


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


3 20
-1 Output: -1

hide comments
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
Min_25: 2017-04-24 10:20:07

The maximum number of queries is around 3000000.

pvsmpraveen: 2017-04-23 14:05:02

There should be an upper limit mentioned on how many values at max will be in present in the list ,
clearly even if all operations are O(1) we cannot run loop 2^31 to even scan them , there much be a mention. Maybe that will help. Thank you

Re: I didn't mention it because it's part of the challenge. Time limit was set carefully to only accept well-designed solution.

Last edit: 2017-04-23 16:38:04
pvsmpraveen: 2017-04-23 05:51:30

4 i: Print data on ith index (0 <= i <= 2^31 - 1)
type 4 : Print data from a specified index (1-based) after the list is sorted ascendingly

These two contradict each other! is it 0 based or 1-based?

Re: Sorry for the ambiguous description. All problem description apply to both input and output format. So, yes, all index are 1-based.

Last edit: 2017-04-23 06:46:15

Added by:Lucas
Time limit:1s-1.350s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)