Fișierul intrare/ieșire: mediana.in, mediana.out Sursă Concurs IQ Academy | Clasa a 10-a
Autor din folclor Adăugată de teodor94Teodor Plop teodor94
Timp execuție pe test 0.2 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

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