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.
- Insert data to the list
- Remove data from the list
- Print an index (1-based) from a specified data after the list was sorted ascendingly
- 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
Input: 3 20
-1 Output: -1
Had anyone solved this problem using Treap, it time limits on me.
Can someone help? I'm using splay trees which should be log n amortized but getting TLE.
For 4th query, you have to print -1 if i (given as input) is 0.
do all elements will be distinct?
Can anyone help i am getting time limit exceed, all operations answered in O(1) but still :( .
Anyone pro here? i need some help...
Thank you MIN_25, that helped me!
The maximum number of queries is around 3000000.
There should be an upper limit mentioned on how many values at max will be in present in the list ,
4 i: Print data on ith index (0 <= i <= 2^31 - 1)