Nộp bài
Điểm:
1100 (thành phần)
Thời gian:
1.5s
Bộ nhớ:
128M
Input:
MEDIAN.inp
Output:
MEDIAN.out
Tác giả:
Dạng bài
Cho một dãy A ban đầu rỗng. Bạn cần thực hiện q truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:
- +\ u: thêm phần tử u vào dãy a. (u \ge 0)
- -\ u: xóa phần tử u khỏi dãy a. Dữ liệu vào đảm bảo dãy a tồn tại phần tử u.
Sau mỗi truy vấn, bạn cần in ra trung vị của dãy A. Trung vị của một dãy C có n phần tử là phần tử lớn thứ [\frac{n + 1}{2}] của dãy C. Nếu dãy A rỗng in ra -1.
Input, Output và Subtasks
Input: (MEDIAN.inp
)
- Dòng đầu tiên gồm số nguyên dương q. (q \le 1000000)
- q dòng tiếp theo, mỗi dòng có dạng + u_i hoặc - u_i miêu tả truy vấn thứ i. (u_i \le 10^9).
Output: (MEDIAN.out
)
- Với mỗi truy vấn, in ra trung vị của dãy A.
Subtasks
- Subtask 1 (20\%): u_i \le 100.
- Subtask 2 (20\%): q \le 1000.
- Subtask 3 (20\%): q \le 10000.
- Subtask 4 (20\%): q \le 100000.
- Subtask 5 (20\%): Không có giới hạn gì thêm.
Sample
Input (MEDIAN.inp
)
5
+ 1
+ 2
+ 3
+ 4
- 2
Output (MEDIAN.out
)
1
1
2
2
3
Note
- Sau truy vấn đầu tiên: A = (1) và có trung vị là 1.
- Sau truy vấn thứ hai: A = (1, 2) và có trung vị là 1.
- Sau truy vấn thứ ba: A = (1, 2, 3) và có trung vị là 2.
- Sau truy vấn thứ tư: A = (1, 2, 3, 4) và có trung vị là 2.
- Sau truy vấn thứ năm: A = (1, 3, 4) và có trung vị là 3.
Bình luận