Train Tracking timer 2s memory 512MB

Every morning the express train goes past the farm, heading to the big city, and every afternoon it goes past in the opposite direction, back to the suburbs. Today, Bessie is taking the time to watch it, both in the morning and in the afternoon.

Bessie knows in advance that the train has N carriages (1 \leq N \leq 10^6), conveniently numbered 0 \dots N-1. Carriage i has an ID number c_i written on it (0 \le c_i \le 10^9). All numbers are visible both in the morning and in the afternoon, so for each carriage Bessie has two opportunities to observe its number. That is, as the train passes by in the morning, Bessie is able to observe c_0, followed by c_1, all the way to c_{N-1}. As the train passes by in the afternoon, she is again able to observe c_0, followed by c_1, all the way to c_{N-1}.

Bessie has picked out an integer K (1 \leq K \leq N), and she wishes to determine the minimum ID number for each contiguous set of K carriages. She has a notebook in which she can perform computations, but it is rather small and her handwriting (hoof-writing?) is rather large. For example, there may not even be enough space to write down all N+1-K minimums. For arcane reasons, Bessie is content with mooing the minimums to the sky as she computes them, so this at least is not an issue.

The train is soon arriving! Help Bessie find the N + 1 - K minimums as the train goes by twice, and make sure she uses her limited notebook size effectively. Her notebook is divided into 5500 sections, conveniently numbered 0 \dots 5499, and each section has the space to store exactly one integer between -2^{31} and 2^{31}-1 inclusive. Initially, each section stores the integer 0.

This is an interactive problem, but you will not be using standard (or file) I/O. In particular, you must implement the following function, which helps Bessie manage her limited notebook space effectively:

void helpBessie(int ID);

As each train car goes by, both in the morning and in the afternoon, your function will be called, and its input will be the ID number on that train car.

Your implementation of the $\texttt{helpBessie}$ function will be able to call these functions:

• int get(int index): gets the value of the integer stored at the given index of Bessie's notebook.

• void set(int index, int value): sets the integer at the given index to the given value.

• void shoutMinimum(int output): instructs Bessie to moo the given number to the skies.

• int getTrainLength(): returns $N$, the number of train carriages.

• int getWindowLength(): returns $K$, the window length.

• int getCurrentCarIndex(): returns the index of the train carriage which is currently passing by.

• int getCurrentPassIndex(): returns $0$ if Bessie is observing the morning pass, and $1$ if she is observing the afternoon pass.

To help you get started with your code, we have provided initial templates for you in C/C++ and Java. Python and Pascal submissions are unfortunately not supported for this problem.

The window minimums must be output in order (so the minimum over carriages $0, 1, \dots, K-1$ must be output before the minimum over carriages $1, 2, \dots, K$ is output, and so forth), but aside from this ordering constraint, your function may output minimums during any of its function calls, at any times. For example, your function may produce no output during some calls, and may produce multiple outputs during other calls.

Bessie has fantastic very-short-term memory, for which reason there is no restriction on memory usage within the $\texttt{helpBessie}$ function, aside from the normal 256MB limit. However, between train cars, Bessie is unable to "remember" anything not contained in the notebook. So between function calls, your program may not persist state except with the $\texttt{get}$ and $\texttt{set}$ calls.

This means:

You are NOT ALLOWED to create any non-constant global or static variables. Any solution doing so will be disqualified. Coaches WILL manually inspect solutions to verify solutions follow the spirit of the problem. Since file I/O is not necessary for this problem, you are also NOT ALLOWED to perform any file I/O in your code.

The total number of $\texttt{set}$ calls plus the total number of $\texttt{get}$ calls made by your program will be limited to $25 \cdot 10^6$ for each test case.

Problem credits: Dhruv Rohatgi