SID  Search Insert Delete
You are given a bunch of data (all are positive 32 bit numbers) to operate on. The only operations on the data are search, insert, and delete. When storing the data you have to remember its rank, that is the original position when the data is being inserted. All successful operations must return the ranks of the data. Failed operations should return NONE as the answer.
Your objective is to execute all of the operations as fast as possible.
Input
The first line of input is N and M, separated by a space, N is the number of initial data. ( 0 <= N < 1000000 ) and M is the number of operations against the data. ( 0 <= M < 1000000).
The second line contains N data, seperated by blanks. All data are positive 32 bits numbers
The next M lines contains operations against the data. Each line contains a symbol and a number, separated by a space.
There are 3 symbols (S, I, D), each representing search, insert, and delete operation.
'S number' tries to find the number in the stored data, and outputs its first rank in the stored data (as originally inserted), or NONE if no such number exists.
'I number' inserts the number into the stored data, and outputs its rank in the stored data. (Data can be duplicated).
'D number' deletes the least ranked number found in the stored data, and outpus its rank, or NONE if no such number originally exists.
Output
There is an output for each executed operation. See the above input description about each operation for the detail of the output.
Example
Input:
10 6
20 12 10 28 20 50 49 8 51 1
S 20
I 3
S 11
D 20
I 2
S 20
Output:
1
11
NONE
1
12
5
hide comments
aseprizal70:
20190223 18:36:32
Last edit: 20190225 10:06:28 

Bhumit:
20160929 13:09:43
Is time limit too hard for Java?


ruizhang:
20160524 23:46:22
It's interesting that unordered_multimap is much faster than unordered_map of (int, queue) even though equal_range() only returns forward iterators. Moreover, unordered_multimap consumes 20x less space. 

mkrjn99:
20151023 07:52:12
Look out for trailing spaces at the end of line. Caused me numerous WAs Last edit: 20151023 07:52:37 

Ivan Sandrk:
20150510 22:37:57
unordered_multimap ftw xD


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140823 06:53:56
Finally AC using normal balanced binary search tree (without huge memory hashing and it's faster) ;)


Sumit Kumar:
20130913 19:00:07
Is the problem with I/O rectified? I'm getting WA not TLE with O(nlogn)! 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130828 23:30:20
Finally AC after a long time :) Great problem @Jimmy Tirtawangsa 

:D:
20130211 08:34:49
If you're having problems, try using unsigned 32bit integers for values. 

:D:
20130208 07:40:07
Well somethings changed since I have an AC now. I will open it for now. Please email me if you think there are still issues. 
Added by:  Jimmy Tirtawangsa 
Date:  20121028 
Time limit:  0.113s0.232s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ADA95 ASM32GCC CCLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14CLANG C99 COBOL FORTRAN GO GOSU JAVA KTLN LUA OBJC OBJCCLANG PASGPC PASFPC PYTHON PYPY PYTHON3 RUST 
Resource:  Own problem 