Trung vị của tập hợp động

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho một tập hợp đa phần tử (multiset) ban đầu rỗng. Thực hiện $Q$ thao tác thuộc một trong ba loại sau:

  • 1 x: Thêm số nguyên $x$ vào tập hợp.
  • 2 x: Xóa đúng một phần tử có giá trị $x$ khỏi tập hợp (đảm bảo $x$ đang tồn tại trong tập hợp).
  • 3: In ra trung vị của tập hợp hiện tại. Nếu tập hợp có $S$ phần tử ($S \ge 1$), trung vị là phần tử nhỏ thứ $\lceil S / 2 \rceil$ (tính từ $1$).
Dữ liệu vào
  • Dòng đầu chứa số nguyên $Q$.
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác.
Dữ liệu ra

Với mỗi thao tác loại 3, in ra trung vị trên một dòng.

Ví dụ
Input Output
7
1 10
1 30
1 20
3
2 20
1 5
3
20
10
Giới hạn
  • $1 \le Q \le 10^5$
  • $-10^9 \le x \le 10^9$
Draft saved