Trung vị lớn nhất
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho dãy số nguyên $a_1, a_2, \dots, a_N$ và số nguyên $K$. Trung vị của một dãy có độ dài $m$ được định nghĩa là phần tử ở vị trí $\lfloor \frac{m + 1}{2} \rfloor$ sau khi sắp xếp dãy đó theo thứ tự không giảm (ví dụ trung vị của [1, 4, 2, 5] là 2, của [1, 4, 2] là 2).
Hãy tìm trung vị lớn nhất trong tất cả các đoạn con liên tiếp của $a$ có độ dài ít nhất là $K$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra
In ra giá trị trung vị lớn nhất tìm được.
Ví dụ
| Input | Output |
|---|---|
| 5 3 |
1 2 3 2 1 | 2 | | 4 2 1 4 3 2 | 3 |
Giới hạn
- $1 \le K \le N \le 2 \cdot 10^5$
- $1 \le a_i \le N$.
Community Discussion