Description

Every morning, an express train passes by the farm on its way to the big city, and every afternoon it comes back to the suburbs. Today, Bessie will watch it both in the morning and in the afternoon.

Bessie knows in advance that the train has $N$ cars, numbered $0\sim N-1$ for convenience. Car $i$ has an ID $c_i$. In both the morning and the afternoon, all the numbers are visible, so Bessie has two chances to observe the ID of each car. That is, when the train goes by in the morning, Bessie can observe $c_0$, then $c_1$, up to $c_{N-1}$. When the train returns in the afternoon, she can again observe $c_0$, then $c_1$, up to $c_{N-1}$.

Bessie chooses an integer $K$, and she wants to compute the minimum ID in every consecutive block of $K$ cars. She has a notebook to help her do computations, but the notebook is quite small, and Bessie’s handwriting (hoof-writing?) is rather large. For example, there might not be enough space to write down all $N+1-K$ minima. For some mysterious reason, Bessie is satisfied with mooing these numbers to the sky when she computes each minimum, so at least that part is not a problem.

The train is coming soon! Help Bessie compute these $N+1−K$ minima after the train passes twice, making sure she uses her limited notebook space efficiently. Her notebook is divided into $5500$ sections, numbered $0\sim 5499$ for convenience, and each section can store exactly one integer in the range $[-2^{31} , 2^{31}-1]$. Initially, each section stores the integer $0$.

Please help Bessie manage her limited notebook space efficiently.

Interactive protocol

This is an interactive problem; you do not need to use standard (or file) input/output. Specifically, you need to implement the following function, which is used to help Bessie manage her limited notebook space efficiently:

void helpBessie(int ID);

Whenever a train car passes by, whether in the morning or in the afternoon, your function will be called with the ID of that car as input.

Your implementation of helpBessie can call the following functions:

• int get(int index): Get the integer value recorded at the given index in Bessie’s notebook (index).
• void set (int index, int value): Set the value at the given index (index) to the given integer (value).
• void shoutMinimum (int output): Tell Bessie to moo a specified number to the sky.
• int getTrainLength(): Return the number of cars $N$.
• int getWindowLength(): Return the window length $K$.
• int getCurrentCarIndex(): Return the index of the car currently passing by.
• int getCurrentPassIndex(): Return $0$ if Bessie is watching the morning pass, and $1$ for the afternoon pass.

To help you get started, we provide an initial C/C++ template. Unfortunately, Python and Pascal are not supported for this problem.

#include "grader.h"

// If you find it necessary, you may import standard libraries here.

void helpBessie(int ID)
{
	// Put your code here.
}

Call void shoutMinimum (int output) to produce output.

The minima for the windows must be output in order (so the minimum of cars $0,1,\cdots ,K−1$ must be output before the minimum of cars $1,2,\cdots ,K$ and so on), but aside from this ordering constraint, your function may output any number of minima during any call. For example, your function may produce no output during some calls and multiple outputs during others.

Bessie has amazing short-term memory, so there is no memory usage limit inside the helpBessie function other than the standard 256 MB limit. However, between cars, Bessie cannot “remember” anything that does not appear in the notebook. Therefore, between two calls of the function, your program cannot preserve any state except via calls to get and set.

This means:

You are not allowed to define any non-constant global or static variables. Any submission that does so will receive zero credit. Coaches will manually check all submissions to verify compliance with the problem requirements. Since this problem does not require file input/output, using any file I/O in the code is also not allowed.

10 3
5 7 9 2 0 1 7 4 3 6

5
2
0
0
0
1
3
3

Hint

For all testdata, $1\le N\le 10^6,0\le c_i\le 10^9,1\le K\le N$, and the total number of set and get calls your program makes is limited to $25\times 10^6$.

Problem by: Dhruv Rohatgi.

Translated by ChatGPT 5