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
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.
|
|
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 :( .
|
|
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!
|
Added by: | Lucas |
Date: | 2017-04-22 |
Time limit: | 1s-1.350s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |