2018年3月USACO美国计算机奥赛Open Contest公开赛白金级题2

USACO 2018 US Open Contest, Platinum Problem 2. Train Tracking

2018年3月USACO美国计算机奥赛公开赛白金级题2

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 NN carriages (1≤N≤1061≤N≤106), conveniently numbered 0…N−10…N−1. Carriage ii has an ID number cici written on it (0≤ci≤1090≤ci≤109). 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 c0c0, followed by c1c1, all the way to cN−1cN−1. As the train passes by in the afternoon, she is again able to observe c0c0, followed by c1c1, all the way to cN−1cN−1.

Bessie has picked out an integer KK (1≤K≤N1≤K≤N), and she wishes to determine the minimum ID number for each contiguous set of KK 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−KN+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−KN+1−K minimums as the train goes by twice, and make sure she uses her limited notebook size effectively. Her notebook is divided into 55005500 sections, conveniently numbered 0…54990…5499, and each section has the space to store exactly one integer between −231−231 and 231−1231−1 inclusive. Initially, each section stores the integer 00.

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 helpBessiehelpBessie 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 NN, the number of train carriages.

int getWindowLength(): returns KK, the window length.

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

int getCurrentPassIndex(): returns 00 if Bessie is observing the morning pass, and 11 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,…,K−10,1,…,K−1 must be output before the minimum over carriages 1,2,…,K1,2,…,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 helpBessiehelpBessiefunction, 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 getget and setset 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 setset calls plus the total number of getget calls made by your program will be limited to 25⋅10625⋅106 for each test case.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

5
2
0
0
0
1
3
3