In this problem, we are asked to find all sliding-window minima in an array, for some fixed-length window. We are given two passes through the array. The catch is that we are given only $O(\sqrt{N})$ memory.

Let $f(i)$ be the location of the smallest element in the range $[i, i+K)$, breaking ties by smallest index. Observe that $f(i) \leq f(i+1)$ for each $i$. So if we compute $f(0), f(B), f(2B), \dots, f(N)$ for some block size $B$ in the first pass, this gives us some information which we may be able to use in the second pass to compute the remaining $f(i)$s.

Let's ignore the constraint on calls to set/get for now. If we let $B = \sqrt{N}$, then we can compute $f(0), f(\sqrt{N}), \dots, f(N)$ in our first pass using only $O(\sqrt{N})$ memory and $O(N\sqrt{N})$ time. Now, in the second pass, observe that for any fixed array element $i$, there are only $O(\sqrt{N})$ windows for which the minimum could possibly be at position $i$.

This suggests the following algorithm for the second pass: read and ignore all elements with index less than $f(0)$. Now maintain running minima for $f(0), f(1), f(2), \dots, f(\sqrt{N})$. Once we've read in the element with index $f(\sqrt{N})$, we know that we have computed the correct minima for the first $\sqrt{N}$ windows. Output these, start maintaining minima for the next $\sqrt{N}$ windows, and continue in the same fashion.

The memory usage of the second pass is also $\sqrt{N}$, as desired. Unfortunately, the time complexity of each pass is $O(N \sqrt{N})$. In particular, the above algorithm would use $O(N \sqrt{N})$ calls to set and get, which would exceed the given bound. To improve the time complexity, we can use a monotonic queue in each pass. In the first pass, for instance, the boundaries of the $\sqrt{N}$ windows define $2\sqrt{N}$ subarrays, and for each subarray we can simply compute the minimum of the subarray and put that into the monotonic queue. The length of the monotonic queue therefore never exceeds $O(\sqrt{N})$, and we can compute the $\sqrt{N}$ minima-locations in $O(N)$ time. For the second pass, it suffices to observe that in each segment of the array (say, between $f(i\sqrt{N})$ and $f((i+1)\sqrt{N})$) all but $O(\sqrt{N})$ of the array elements are in all $\sqrt{N}$ windows of interest. This once again allows us to improve the pass to $O(N)$ time will not exceeding $O(\sqrt{N})$ memory.

Below is an implementation of the above algorithm.

#include "grader.h"
#define BLOCK 1000
#define DIF 4050

// VARIABLE - LOCATION IN BESSIE'S NOTEBOOK
// back index - 0
// top index - 1
// queue (2,3) (4,5) ...
//       (index, value)
// current block's endpoint index (divided by BLOCK) - DIF-1
// current block's global low - DIF-2
// number of minima output - DIF-3

void helpBessie(int v)
{
	int N = getTrainLength();
	int K = getWindowLength();
	int i = getCurrentCarIndex();
	int p = getCurrentPassIndex();
	if(p==0)
	{
		if(i==0)
		{
			set(0,0);
			set(1,-1);
		}
		int top = get(1);
		int back = get(0);
		if(i%BLOCK == 0 || (i>=K && (i-K)%BLOCK == 0))  // reached boundary of some window
		{						// need to make new entry in monotonic queue
			while(top >= back && get(2*top+3) >= v)
				top--;
			top++;
			set(2*top+2,i);
			set(2*top+3,v);
		}
		else	//still part of same subarray; just update the top entry of monotonic queue
		{
			int curTopValue = get(2*top+3);
			if(v <= curTopValue)
			{
				top--;
				while(top >= back && get(2*top+3) >= v)
					top--;
				top++;
				set(2*top+2,i);
				set(2*top+3,v);
			}
		}
		if(i >= K-1 && (i+1-K)%BLOCK == 0)	// at endpoint of some window; need to store location of minimum
		{
			while(top >= back && get(2*back+2) <= i-K)	// pop from back end up queue until queue contains only
				back++;					// elements in desired window
			set(DIF + (i+1-K)/BLOCK, get(2*back+2));	// store location of minimum
		}
		set(0,back);
		set(1,top);
	}
	else
	{
		if(i < get(DIF))
			return;
		if(i == get(DIF))
		{
			set(0,0);
			set(1,-1);
			set(DIF-1, 1);
			set(DIF-2,1000000000);
			set(DIF-3, 0);
		}
		int bc = get(DIF-1);
		int top = get(1);
		int back = get(0);
		int outputs = get(DIF-3);
		if(i - get(DIF+bc-1) <= BLOCK)  // element may not be contained in all relevant windows
		{				// so add to monotonic queue
			while(top >= back && get(2*top+3) >= v)
				top--;
			top++;
			set(2*top+2,i);
			set(2*top+3,v);
		}
		else 	// element is contained in all relevant windows
		{	// so we can update a global minimum
			int globalLow = get(DIF-2);
			if(v < globalLow)
				set(DIF-2,v);
		}
		if(outputs + K - 1 == i)	//need to output a minimum
		{
			while(top >= back && get(2*back+2) < outputs)
				back++;
			shoutMinimum(min(get(DIF-2),get(2*back+3)));
			outputs++;
		}
		while(BLOCK*bc + K-1 < N && get(DIF+bc) == i) // reached boundary of current subarray
		{
			while(outputs <= BLOCK*bc) // output minimums for all remaining windows in current block
			{
				while(top >= back && get(2*back+2) < outputs)
					back++;
				shoutMinimum(min(get(DIF-2),get(2*back+3)));
				outputs++;
			}
			bc++;
			set(DIF-2,1000000000);
			top = back = 0;
			set(2*top+2,i);
			set(2*top+3,v);
		}
		set(DIF-3,outputs);
		set(DIF-1,bc);
		set(1,top);
		set(0,back);
	}
}