Trung vị lớn nhất

Binary-search Buổi 13 — Chặt nhị phân đáp án prefix-sum
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$.
Draft saved