Official Editorial

Explanation

We can binary search over the largest possible median that is possible to achieve.

To check whether the median $x$ is achievable on an interval, we need to count the number of elements that are $\ge x$ and the number of elements that are $< x$.

If the number of elements $\ge x$ is greater than the number of elements $< x$, we can say that this median is achievable. Note that there must be strictly more elements greater than or equal to $x$ than less than $x$ because of how the problem defines the median for subarrays even sizes.

Let $f(i)$ be the number of elements in the prefix that are$\ge x$ - the number of elements in the prefix that are $< x$.

We can prove that if $f(i) - f(j) > 0$ and $i >= j + k$, it is possible to have a median of $x$. This is because on the range from $i$ to $j$ there will be more elements greater than or equal to $x$ than less than $x$ which means that the median will also be greater than or equal to $x$.

From here we can perform a linear search for the max difference keeping track of the minimum element in the prefix from $0$ to $f[i - k]$ which ensures that the size is always at least $k$. If it greater than $0$, then this median is possible to achieve.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int &i : a) { cin >> i; }

	// Binary search for the maximum median

Copy
import java.io.*;
import java.util.*;

public class MaxMedian {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());

Copy
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

# Binary search over the maximum median
lo = 1
hi = n
while lo < hi:
	median = (lo + hi + 1) // 2
	# Same as the f described in the editorial
	f = []