Explanation

Instead of directly processing each command one-by-one, we can instead process every addition operation once we have to extract our numbers. This allows us for more foresight when it comes to which numbers we prioritize.

If we have $\leq 3$ elements to process, then we arbitrarily put each element in an empty container, and pop those respective containers.

Among the three container types, the deque is the most flexible operation wise. On the other hand, the stack and queue are relatively inflexible. Because we are processing all of our addition commands at once, we can figure out the biggest three elements that have been added, and prioritize those.

For the largest two elements, we can place them into our stack and queue once we encounter them. For our third largest element, our strategy is to always keep it at either the front or back once we insert it into our deque, and place any new elements on the opposite side. This guarantees that we can always extract the biggest three elements inserted.

Implementation

Time Complexity: $\mathcal{O}(N\log{N})$

Copy
#include <bits/stdc++.h>

using ll = long long;

int main() {
	int n;
	std::cin >> n;

	std::vector<int> nums;
	std::priority_queue<int> best;

Copy
import java.io.*;
import java.util.*;

public class DimaContainers {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(r.readLine());

		List<Integer> nums = new ArrayList<>();

Copy
operations = []
nums = []

for _ in range(int(input())):
	i = int(input())

	if i == 0:
		# keep track of the 3 biggest elements
		top3 = sorted(nums)[-3:]