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