Informática – Nivel Avançado – Semana 18

—

por

Leonardo Paes

Dois Tipos de Feitiços

Flúcio está jogando um jogo de computador. Neste jogo, ele luta contra monstros usando feitiços mágicos.

Existem dois tipos de feitiços: o feitiço de fogo de poder $$x$$ que causa $$x$$ dano ao monstro e o feitiço de raio de poder $$y$$ que causa $$y$$ de dano ao monstro e dobra o dano do próximo feitiço que Flúcio lançar. Cada feitiço pode ser lançado apenas uma vez por batalha, mas Flúcio pode lançá-los em qualquer ordem.

Por exemplo, suponha que Flúcio conheça três feitiços: um feitiço de fogo de poder $$5$$, um feitiço de raio de poder $$1$$ e um feitiço de raio de poder $$8$$. Existem $$6$$ maneiras de escolher a ordem em que ele lança os feitiços:

  • primeiro, segundo, terceiro. Esta ordem causa $$5 + 1 + 2*8 = 22$$ de dano;
  • primeiro, terceiro, segundo. Esta ordem causa $$5 + 8 + 2*1 = 15$$ de dano;
  • segundo, primeiro, terceiro. Esta ordem causa $$1 + 2*5 + 8 = 19$$ de dano;
  • segundo, terceiro, primeiro. Esta ordem causa $$1 + 2*8 + 2*5 = 27$$ de dano;
  • terceiro, primeiro, segundo. Esta ordem causa $$8 + 2*5 + 1 = 19$$ de dano;
  • terceiro, segundo, primeiro. Esta ordem causa $$8 + 2*1 + 2*5 = 20$$ de dano.

Inicialmente, Flúcio conhece $$0$$ feitiços. Seu conjunto de feitiços muda $$n$$ vezes, cada vez ele aprende um novo feitiço ou esquece um já conhecido. Após cada mudança, calcule o dano máximo possível que Flúcio pode causar usando os feitiços que ele conhece.

Entrada:

A primeira linha contém um inteiro $$n$$ – o número de mudanças no conjunto de feitiços.

Cada uma das próximas $$n$$ linhas contém dois inteiros $$tp$$ e $$d$$ – a descrição da mudança. Se $$tp_i$$ for igual a $$0$$, então Flúcio aprende (ou esquece) um feitiço de fogo, caso contrário, ele aprende (ou esquece) um feitiço de raio.

Se $$d_i > 0$$, então Flúcio aprende um feitiço de poder $$d_i$$. Caso contrário, Flúcio esquece um feitiço com poder $$-d_i$$, e é garantido que ele conhecia aquele feitiço antes da mudança.

É garantido que os poderes de todos os feitiços que Flúcio conhece após cada mudança são diferentes (Flúcio nunca conhece dois feitiços com o mesmo poder).

Saída:

Após cada mudança, imprima o dano máximo que Flúcio pode causar com seu conjunto atual de feitiços.

Restrições:

  • $$1 \leq n \leq 2*10^5$$;
  • $$0 \leq tp_i \leq 1$$;
  • $$-10^9 \leq d_i \leq 10^9$$;

Exemplo:

Entrada Saida
6
1 5
0 10
1 -5
0 5
1 11
0 -10		 5
25
10
15
36
21

Para submeter sua solução, use esse link.