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

Problem credits: Dhruv Rohatgi

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > US Open > Platinum