Trung Vị Trực Tuyến
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho một dãy số được thêm lần lượt. Sau mỗi lần thêm một phần tử, hãy in ra trung vị (median) của dãy hiện tại.
Trung vị là phần tử ở giữa khi dãy được sắp xếp. Nếu dãy có số phần tử chẵn, trung vị là phần tử ở vị trí $\lfloor(n+1)/2\rfloor$ (1-indexed) trong dãy đã sắp.
Dữ liệu vào
- Dòng đầu: số nguyên dương $N$ $(1 \le N \le 10^5)$.
- Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^9)$.
Dữ liệu ra
- In $N$ dòng, dòng thứ $i$ là trung vị sau khi thêm $a_i$.
Ví dụ
| Input | Output |
|---|---|
| 5\n5 2 8 1 4 | 5\n2\n5\n2\n4 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion