Fişierul intrare/ieşire:mediana.in, mediana.outSursăConcurs IQ Academy | Clasa a 10-a
AutorDin FolclorAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.2 secLimită de memorie3072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile 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.inmediana.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 sa te autentifici pentru a trimite solutii. Click aici