Phần tử trung vị


Submit solution

Points: 3
Time limit: 1.5s
Python 3 15.0s
Memory limit: 977M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Tichpx dạy môn xử lý ảnh có thuật toán lọc trung vị, đây là một thuật toán cần phải tìm trung vị của histogram. Trung vị của một dãy n phần tử \(a_1, a_2, ... a_n\) là phần tử mà khi sắp xếp dãy tăng dần thì nó ở giữa dãy đó là \(a[(n+1)/2]\). Chẳng hạn trung vị của dãy {1,3,4,5} có 4 phần tử trung vị là a[(4+1)/2]=a[2]= 3 còn trung vị của dãy {1,3,4,5,5} thì trung vị là a[(5+1)/2]=a[3]=4;

Bài toán đặt ra là bạn lần lượt bổ sung n phần tử vào dãy với mỗi phần tử thứ i bổ sung vào thì xuất ra trung vị của dãy con \(a_1, a_2,... a_i\)

Input

Dòng đầu là số nguyên dương n \((1<= n <=10^6)\)

Dòng tiếp theo chứa n phần tử có giá trị tuyệt đối không vượt quá 32767.

Output

Xuất ra n giá trị trung vị của các dãy con tiếp đầu của dãy đã cho

Ví dụ

Input

9
7 4 2 1 6 8 5 8 7

Output

7 4 4 2 4 4 5 5 6

Giải thích : Ban đầu dãy rỗng ta bổ sung lần lượt

  • Bổ sung 7 nên dãy con sau khi săp {7} -> trung vị 7

  • Bổ sung 4 nên dãy con sau khi săp {4, 7} -> trung vị 4

  • Bổ sung 2 nên dãy con sau khi sắp {2, 4, 7} -> trung vị 4

  • Bổ sung 1 nên dãy con sau khi sắp {1, 2, 4, 7} -> trung vị 2

  • Bổ sung 6 nên dãy con sau khi sắp {1, 2, 4, 6, 7} -> trung vị 4

  • Bổ sung 8 nên dãy con sau khi sắp {1, 2, 4, 6, 7, 8} -> trung vị 4

  • Bổ sung 5 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 8} -> trung vị 5

  • Bổ sung 8 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 8, 8} -> trung vị 5

  • Bổ sung 7 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 7, 8, 8} -> trung vị 6

tichpx

Comments


  • 2
    cotyey  commented on Oct. 4, 2019, 3:01 p.m.

    custom binary tree N * log(N): https://ideone.com/jwiM89


    • 1
      TICHPX  commented on Oct. 7, 2019, 4:28 p.m.

      Cừ dạo này code cây ác liệt


      • 1
        cotyey  commented on Oct. 10, 2019, 1:17 p.m.

        e đang cày pro bên ss, chủ yếu code tay to, ko dùng thu viện, dùng gì code lại xD nên vào đây test xD


  • 3
    TICHPX  commented on Oct. 8, 2018, 5:34 a.m.

    Test 10^6 chặt quá thời gian