Dynamic Median

Xem dạng PDF

Gửi bài giải

Điểm: 0,87 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \dots N]~ được sắp xếp không giảm là phần tử ~a\left[\frac{N + 1}{2}\right]~.

Input

Dòng đầu tiên chứa ~Q~ là số truy vấn. ~( 1 \leq Q \leq 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

20
+ 6
+ 2
+ 5
+ 3
+ 6
- 3
+ 8
- 6
- 5
+ 5
+ 2
- 8
+ 5
+ 5
- 2
+ 1
- 5
+ 4
+ 8
+ 7

Sample Output

6
2
5
3
5
5
6
5
6
5
5
2
5
5
5
5
5
4
5
5

Note

~\begin{array}{lll} \mbox{Input} & \mbox{Output} & \mbox{Explanation} \\ 20 & 6 & {[}6{]} \\ +6 & 2 & {[}2, 6{]} \\ +2 & 5 & {[}2, 5, 6{]} \\ +5 & 3 & {[}2, 3, 5, 6{]} \\ +3 & 5 & {[}2, 3, 5, 6, 6{]} \\ +6 & 5 & {[}2, 5, 6, 6{]} \\ -3 & 6 & {[}2, 5, 6, 6, 8{]} \\ +8 & 5 & {[}2, 5, 6, 8{]} \\ -6 & 6 & {[}2, 6, 8{]} \\ -5 & 5 & {[}2, 5, 6, 8{]} \\ +5 & 5 & {[}2, 2, 5, 6, 8{]} \\ +2 & 2 & {[}2, 2, 5, 6{]} \\ -8 & 5 & {[}2, 2, 5, 5, 6{]} \\ +5 & 5 & {[}2, 2, 5, 5, 5, 6{]} \\ +5 & 5 & {[}2, 5, 5, 5, 6{]} \\ -2 & 5 & {[}1, 2, 5, 5, 5, 6{]} \\ +1 & 5 & {[}1, 2, 5, 5, 6{]} \\ -5 & 4 & {[}1, 2, 4, 5, 5, 6{]} \\ +4 & 5 & {[}1, 2, 4, 5, 5, 6, 8{]} \\ +8 & 5 & {[}1, 2, 4, 5, 5, 6, 7, 8{]} \\ +7 & & \end{array}~


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    This_is_a_name  đã bình luận lúc 9, Tháng 10, 2021, 12:34

    Nếu tập hợp rỗng thì xuất ra gì nhỉ :v ?


    • 2
      SPyofgame  đã bình luận lúc 9, Tháng 10, 2021, 16:11

      Bạn đọc kĩ đề nhé thinkingcat

      (bộ test đảm bảo tồn tại phần tử ~x~ trong tập hợp).


      • 0
        This_is_a_name  đã bình luận lúc 9, Tháng 10, 2021, 16:26 sửa 2

        cảm ơn bạn

        mình tưởng x đó là phần tử nhập vào khi xóa :vv


  • 12
    CQTshadow  đã bình luận lúc 6, Tháng 10, 2021, 18:16

    Lời giải của Team mình, lưu ý chỉ nên xem khi đã bí cách cũng như bất lực để việc học hiệu quả.

    Unofficial Solution:

    https://hackmd.io/@Editorial-Slayers/medquery - click