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: 2019-02-23 18:36:32

Last edit: 2019-02-25 10:06:28
Bhumit: 2016-09-29 13:09:43

Is time limit too hard for Java?
TLE even with fast I/O and HashMap. :/

ruizhang: 2016-05-24 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: 2015-10-23 07:52:12

Look out for trailing spaces at the end of line. Caused me numerous WAs

Last edit: 2015-10-23 07:52:37
Ivan Sandrk: 2015-05-10 22:37:57

unordered_multimap ftw xD

the test cases need updating, there has to be a test case where all the numbers are the same (so solutions implementing a hash table deteriorate to O(N))

(Tjandra Satria Gunawan)(曾毅昆): 2014-08-23 06:53:56

Finally AC using normal balanced binary search tree (without huge memory hashing and it's faster) ;-)
And I solve this problem using the same technique to solve ORDERSET, the fun is I'm rank#4 on this and that problem :-D
EDIT: I delete some unused debug process on my code, now I'm #3 on this problem.

Last edit: 2014-08-23 07:10:29
Sumit Kumar: 2013-09-13 19:00:07

Is the problem with I/O rectified? I'm getting WA not TLE with O(nlogn)!

(Tjandra Satria Gunawan)(曾毅昆): 2013-08-28 23:30:20

Finally AC after a long time :-) Great problem @Jimmy Tirtawangsa

:D: 2013-02-11 08:34:49

If you're having problems, try using unsigned 32-bit integers for values.

:D: 2013-02-08 07:40:07

Well somethings changed since I have an AC now. I will open it for now. Please e-mail me if you think there are still issues.


Added by:Jimmy Tirtawangsa
Date:2012-10-28
Time limit:0.113s-0.232s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32-GCC C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL FORTRAN GO GOSU JAVA KTLN LUA OBJC OBJC-CLANG PAS-GPC PAS-FPC PYTHON PYPY PYTHON3 RUST
Resource:Own problem