MEDQUERY - Dynamic Median
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/C
Yêu cầu :
Hãy quản lí một tập hợp các số nguyên không âm hỗ trợ các thao tác sau:
1. Thêm một phân tử
2. Xóa một phần tử
3. Tìm trung vị của tập hợp
Định nghĩa trung vị:
Trung vị của dãy a[1..N] được sắp xếp không giảm là phần tử a[(N+1)/2].
Input
Dòng đầu tiên chứa Q là số truy vấn. (1 <= Q <= 10^6)
Q dòng tiếp theo, mỗi dòng gồm một kí tự '+' hoặc '-' và một số nguyên không âm nhỏ hơn 10^9. Dấu '+' biểu thị thao tác thêm phần tử x vào tập hợp (có thể tập hợp đã có phần tử x nhưng thao tác này vẫn được thực hiện). Dấu '-' biểu thị thao tác xóa phần tử x khỏi tập hợp (bộ test đảm bảo tồn tại phần tử x trong tập hợp).
Output
Q dòng, mỗi dòng là trung vị của tập hợp sau mỗi thao tác thêm/xóa.
Sample
Input
Output
Explanation
20
+ 6
+ 2
+ 5
+ 3
+ 6
- 3
+ 8
- 6
- 5
+ 5
+ 2
- 8
+ 5
+ 5
- 2
+ 1
- 5
+ 4
+ 8
+ 7
6
2
5
3
5
5
6
5
6
5
5
2
5
5
5
5
5
4
5
5
[6]
[2, 6]
[2, 5, 6]
[2, 3, 5, 6]
[2, 3, 5, 6, 6]
[2, 5, 6, 6]
[2, 5, 6, 6, 8]
[2, 5, 6, 8]
[2, 6, 8]
[2, 5, 6, 8]
[2, 2, 5, 6, 8]
[2, 2, 5, 6]
[2, 2, 5, 5, 6]
[2, 2, 5, 5, 5, 6]
[2, 5, 5, 5, 6]
[1, 2, 5, 5, 5, 6]
[1, 2, 5, 5, 6]
[1, 2, 4, 5, 5, 6]
[1, 2, 4, 5, 5, 6, 8]
[1, 2, 4, 5, 5, 6, 7, 8]
- Người up: ladpro98