Solução por Pedro Racchetti
Conteúdos Utilizados:
Para esse problema, podemos utilizar dois $$multisets$$, um para manter os números menores que a mediana, e um para manter os números maiores que a mediana. Para isso, guardaremos quantos números no total estamos analisando.
Quando recebermos uma bolacha nova, e o total de números for ímpar, basta inserir-lo na estrutura de números maiores, e trazer o menor número dela para a estrutura de números menores, e então aumentar o total de números. Caso o total de números for par, faremos o processo contrário, inserindo o número na estrutura de menores, e passando o maior número dessa estrutura para a estrutura de maiores.
Com isso, podemos perceber que para calcularmos a mediana, basta usarmos o menor número da estrutura dos maiores, e então removê-lo. Porém, para mantermos essa propriedade, quando o total de números for par antes de remover, precisaremos mover o maior número da estrutura dos maiores para a estrutura dos menores, já que essa será a mediana agora.
Segue o código, comentado, para melhor compreensão:
https://gist.github.com/PedroRacchetti/47144abe88f470cb97c139b3cf200ef8