trang chủ / đề bài / icpc22_mb_h

Trung vị

Đề bài

Mô tả

Thầy Phương đang tổ chức một học phần "Lập trình thi đấu" đặc biệt để chuẩn bị cho học sinh của mình tham dự kỳ thi ICPC sắp tới.

Tại mọi thời điểm, thầy Phương muốn tính trung vị năng lực của cả lớp để có thể chọn một bộ đề phù hợp với năng lực của học sinh.

Lớp có N học sinh, đánh số từ 0 đến N−1, với năng lực a[i] được sắp xếp theo thứ tự không giảm.

  • Nếu N lẻ, trung vị bằng a[N/2] (phép chia lấy phần nguyên).
  • Nếu N chẵn, trung vị bằng (a[N/2−1]+a[N/2])/2.

Có Q sự kiện, mỗi sự kiện thuộc một trong 3 loại:

  • IN x: một học sinh có năng lực x vào lớp;
  • OUT x: một học sinh có năng lực x rời lớp;
  • MEDIAN: thầy Phương muốn biết giá trị trung vị hiện tại.

Hãy giúp thầy Phương trả lời các câu hỏi.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên Q là số sự kiện.

Q dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng ở trên.

Ban đầu lớp không có học sinh nào. Khi có sự kiện OUT x, đảm bảo trong lớp đang có ít nhất một học sinh năng lực x (đã vào bằng một sự kiện IN x trước đó và chưa rời đi); sự kiện này chỉ làm đúng một học sinh như vậy rời lớp. Nhiều học sinh có thể có cùng năng lực.

Dữ liệu ra

Với mỗi sự kiện MEDIAN, in ra trên một dòng giá trị trung vị tại thời điểm đó. Trung vị luôn là số nguyên hoặc số nguyên cộng 0,5: in số nguyên ở dạng thông thường, còn trường hợp sau in phần nguyên, tiếp theo là ".5" (dấu chấm thập phân), ví dụ 1.5.

Ràng buộc

  • 1≤Q≤2×105.
  • 0≤x≤109.
  • Khi có sự kiện MEDIAN, lớp có ít nhất một học sinh; có ít nhất một sự kiện MEDIAN.

Ví dụ

Input Output Giải thích
22
IN 1
MEDIAN
IN 2
MEDIAN
IN 3
MEDIAN
IN 4
MEDIAN
IN 5
MEDIAN
OUT 1
MEDIAN
IN 6
MEDIAN
OUT 2
MEDIAN
IN 7
MEDIAN
OUT 5
MEDIAN
IN 8
MEDIAN
1
1.5
2
2.5
3
3.5
4
4.5
5
5
6
Ví dụ, sau OUT 1 lớp gồm 2,3,4,5 nên trung vị là (3+4)/2=3,5.
10
IN 5
IN 5
IN 1
MEDIAN
OUT 5
MEDIAN
IN 1000000000
MEDIAN
OUT 1
MEDIAN
5
3
5
500000002.5
OUT 5 chỉ làm một trong hai học sinh năng lực 5 rời lớp, lớp còn 1,5. Cuối cùng lớp gồm 5 và 109.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0