Data structure that keeps elements in chronological order, allows erases in O(log(n)) or less, and allows insertions.

→ Pay attention

Before contest
Codeforces Round 995 (Div. 3)
01:00:11
Register now »

→ Streams

Codeforces Round 995 Solution Discussion

By aryanc403

Before stream 03:20:10

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

Qualified's blog

Data structure that keeps elements in chronological order, allows erases in O(log(n)) or less, and allows insertions.

By Qualified, history, 4 years ago, In English

I want a data structure that keeps elements in the way that you inserted them and allows erases in $$$O(log(n))$$$ or less. For example, if the initial array is empty and you insert 5, 2, 4, then the array would be [5, 2, 4]. Erase 4 and it is [5, 2]. Insert a 3 and it is [5, 2, 3]. I know that set allows erases in $$$O(log(n))$$$ and insertions but it keeps the elements in sorted order, not in the way that I inserted them.

Qualified
4 years ago
4

Comments (4)

Write comment?

Qualified

4 years ago, # |

Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).

→ Reply

navneet.h

4 years ago, # |

+16

Self understandable code

struct DS
{
	set<pair<int,int>> st;
	map<int,int> idx;
	int time = 0;
	void insert(int x){
		st.insert({idx[x] = time++, x});
	}
	void erase(int x){
		auto itr = st.find({idx[x],x});
		if(itr == st.end()) {cout << "Element does not exist\n";}
		else st.erase(itr);
	}
	void printDS(){
		for(auto pr: st){
			cout << pr.second << " ";
		}
		cout << "\n";
	}
};

→ Reply

_dp95

4 years ago, # ^ |

+13

You can get rid of the log factor to achieve O(1) for Insert and Delete operations by using std::list and std::unordered_map.

Code

struct DS{
    list<int> lst ;
    unordered_map< int, list<int>::iterator > has ;
    void insert( int x ){
        lst.push_back( x ) ;
        has[x] = --lst.end() ;
    }
    void erase( int x ){
        if(has.find(x)==has.end()){
            cout << "Element not found" << '\n' ;
            return ;
        }
        lst.erase(has[x]);
        has.erase(x) ;
    }
    void print(){
        for(auto itr:lst)
            cout << itr << " " ;
        cout << '\n' ;
    }
};

→ Reply

Codeforcer

4 years ago, # ^ |

You need to insert a good hash else it is bound to be hacked.

https://codeforces.net/blog/entry/62393

→ Reply