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
scanf is too slow , you should use fread.
"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???
I am also searchng for a Treap solution. I am getting TLE, but all my queries are log(n). Can anyone share?
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!