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

    ID: 1599 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open18来源:usaco.orgscoring:equal_test_cases单调队列

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

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

题目描述

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 \leq N \leq 10^6), conveniently numbered 0…N−10 \dots N-1. Carriage ii has an ID number cic_i written on it (0≤ci≤1090 \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 c0c_0, followed by c1c_1, all the way to cN−1c_{N-1}. As the train passes by in the afternoon, she is again able to observe c0c_0, followed by c1c_1, all the way to cN−1c_{N-1}. Bessie has picked out an integer KK (1≤K≤N1 \leq K \leq 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 \dots 5499, and each section has the space to store exactly one integer between −231-2^{31} and 231−12^{31}-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 helpBessie\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 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, \dots, K-1 must be output before the minimum over carriages 1,2,…,K1, 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 helpBessie\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 get\texttt{get} and set\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 set\texttt{set} calls plus the total number of get\texttt{get} calls made by your program will be limited to 25⋅10625 \cdot 10^6 for each test case.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

10 3
5 7 9 2 0 1 7 4 3 6
5
2
0
0
0
1
3
3
Problem credits: Dhruv Rohatgi