Hello codeforces community,

I've just encountered a (pretty obvious) data structure task in a mini-competition held by kevinxiehk.

Summary of the task: n operations, 3 types.

Insert ID

`x`

on the right sideRemove from the left side

Sort by ID

1 <= n <= 5x10^5, 0 <= x <= 10^9

During the contest, I was able to solve the subtask n <= 2000 and got TLE for the last subtask (full solution). I used `multiset`

and the code is as followed.

Time limit: 2s

```
// implementation I, using multiset
// 56/100, TLE
void solve () {
int n; cin >> n;
int op, x;
multiset<int> s;
queue<int> smallest;
for (int i = 1; i <= n; i++) { // O(n)
cin >> op;
if (op == 1) {
cin >> x;
s.insert(x); // O(n log n)
smallest.push(x);
}
else if (op == 2) {
if (!smallest.empty()) {
cout << smallest.front() << "\n";
auto pos = s.find(smallest.front()); // O(log n)
s.erase(pos); // amortized O(1)
smallest.pop();
}
else if (!s.empty()) {
cout << *(s.begin()) << '\n';
s.erase(s.begin()); // amortized O(1)
}
else cout << "-1\n";
}
else {
while (!smallest.empty()) smallest.pop(); // O(n)
for (auto x : s) smallest.push(x); // O(n)
}
}
// the overall time complexity should be O(n log n), ignoring the O(n) popping of the queue and insertion to the queue of type 3 operation
}
```

After the contest, I noticed that the suggested solution's algorithm is actually the same, but using `priority_queue`

instead of `multiset`

.

Blaming myself for forgetting `priority_queue`

, I found out that the time complexity for both solutions should be the same.

My accepted code:

```
// implementation II, using priority_queue
// 100/100, AC
void solve () {
int n; cin >> n;
int op, x;
priority_queue<int, vector<int>, greater<int>> pq;
queue<int> q;
vector<int> v;
for (int i = 1; i <= n; i++) { // O(n)
cin >> op;
if (op == 1) {
cin >> x;
q.push(x);
}
else if (op == 2) {
if (!pq.empty()) { // O(log n)
cout << pq.top() << '\n';
pq.pop();
}
else if (!q.empty()) {
cout << q.front() << '\n';
q.pop();
}
else cout << "-1\n";
}
else {
while (!q.empty()) { //worst case O(n)
pq.push(q.front()); // O(log n)
q.pop();
}
}
}
// the overall time complexity should be O(n log n), ignoring the O(n) popping of the queue and insertion to the queue of type 3 operation
}
```

I googled up whether `priority_queue`

or `multiset`

is better for these kinds of operations. The result is that `priority_queue`

is indeed faster than `multiset`

.

However, in the task above, popping from a `priority_queue`

should be O(log n), and erasing an element using pointers in `multiset`

should be amortized O(1).

I still don't understand why the `multiset`

solution cannot pass the time limit, even with `cin.tie()->sync_with_stdio(false)`

. Please comment below, your help will be highly appreciated.

Thank you once again for reading.

If you wonder what is in the `main`

function, it's just contain `cin.tie()->sync_with_stdio(false);`

and calling `solve()`