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