### ml7code's blog

By ml7code, history, 2 years ago,

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.

1. Insert ID x on the right side

2. Remove from the left side

3. 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()

• -2