Fișierul intrare/ieșire mediana.in, mediana.out Sursă Concurs IQ Academy | Clasa a 10-a
Autor din folclor Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.2 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Mediana (clasa a 10-a)

Numim mediana unui vector cu N elemente valoarea care se află pe poziția (N + 1) / 2 după sortarea elementelor în ordine crescătoare.

Cerință

Avem un vector care este inițial gol. Se dau Q operații de forma:

  • 1 X: adăugați numărul X în vector
  • 2: afișați mediana vectorului

Date de intrare

Fișierul de intrare mediana.in conține pe prima linie numărul natural Q, iar pe următoarele Q linii operațiile descrise în enunț.

Date de ieșire

În fișierul de ieșire mediana.out se vor găsi răspunsurile operațiilor de tip 2, fiecare răspuns pe câte o linie.

Restricții

  • 1 ≤ Q ≤ 100.000
  • 1 ≤ X ≤ 109
  • Se garantează că prima operație nu este de tip 2.

Exemplu

mediana.in mediana.out
10
1 2
1 3
1 1
1 4
1 5
2
1 6
1 7
1 8
2
3
4

Explicație

Pentru prima întrebare, vectorul este {2, 3, 1, 4, 5}. Îl vom ordona crescător: {1, 2, 3, 4, 5}. Deci mediana este 3.
Pentru cea de-a doua întrebare, vectorul ordonat crescător este {1, 2, 3, 4, 5, 6, 7, 8}. Deci mediana este 4.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii