| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MEDQUERY - Dynamic Median |
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] |
| Được gửi lên bởi: | Le Anh Duc - A2K42 PBC |
| Ngày: | 2017-02-05 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
hide comments
|
2017-11-19 14:08:20
Nếu không có phần tử nào ghi ra 0 -_- |
|
|
2017-02-23 18:15:25 Lollipop
heap |
|
|
2017-02-06 06:26:16
time 1s mà chưa thấy ai ac dưới 1s :V phanduy16 Last edit: 2017-02-06 06:27:19 |
RSS