#2870. 「USACO 2018 US Open Platinum」Train Tracking

内存限制:9 MiB 时间限制:1000 ms 题目类型:交互
上传者: HeRaNO

题目描述

每天早晨特快列车会经过农场,开往大城市,每天下午它又会折回来,回到郊区。今天,Bessie 会花时间观察它,早晨和下午都会。

Bessie 提前知道,列车有 N 节车厢,方便起见,将其编号为 0\sim N−1 。车厢 i 有一个 ID c_i 。在早晨和下午,所有的数字都是可见的,所以对于每节车厢 Bessie 有两次机会观察它的 ID。也就是说,当列车早晨经过的时候,Bessie 能够观察 c_0 ,然后是 c_1 ,直到 c_{N−1} 。当列车下午驶回的时候,她又一次能够观察 c_0 ,然后是 c_1 ,直到 c_{N−1}

Bessie 挑选了一个整数 K ,她想要求出每个连续的 K 节车厢中最小的 ID。她有一本能够帮助执行计算的笔记本,但是这个笔记本相当小,并且 Bessie 的手写(蹄写?)字相当大。比方说,可能没有足够的空间记下所有 N+1-K 个最小值。由于某些神秘的原因,Bessie 满足于当她算出最小数的时候向天哞出这些数,所以这个问题至少还不成问题。

列车马上就要来了!帮助 Bessie 在列车经过两次之后求出这 N+1−K 个最小数,确保她有效地利用她有限的笔记本空间。她的笔记本被分为 5500 个部分,方便起见编号为 0\sim 5499 ,每个部分的空间恰好能够记录一个在 [−2^{31} , 2^{31}−1] 之间的整数。最初的时候,每个部分都记录着整数 0

请帮助 Bessie 有效管理她有限的笔记本空间。

输入格式

这是一道交互式题目,你不需要使用标准(或文件)输入输出。具体地说,你需要实现下面的函数,这个函数用来帮助 Bessie 有效管理她有限的笔记本空间:

void helpBessie(int ID);

每当一节列车车厢经过的时候,无论是在早晨和下午,你的函数都会被调用,函数的输入是这节车厢的 ID。

你的 helpBessie 函数的实现可以调用下面这些函数:

  • int get(int index):获取记录在 Bessie 的笔记本上的给定的索引处的整数值(index)。
  • void set (int index, int value):设置给定的索引(index)处的值为给定的整数值(value)。
  • void shoutMinimum (int output):通知 Bessie 向天哞一个指定的数。
  • int getTrainLength():返回列车的车厢数 N
  • int getWindowLength():返回窗口的长度 K
  • int getCurrentCarIndex():返回当前正在通过的车厢编号。
  • int getCurrentPassIndex():如果 Bessie 正在观察早晨的列车返回 0 ,下午的列车返回 1

为了帮助你开始编码,我们为你提供了初始的 C/C++ 模板。遗憾地,这道题目不支持 Python 和 Pascal 语言的程序。

#include "grader.h"

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

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

输出格式

调用 void shoutMinimum (int output) 函数进行输出。

各个窗口的最小数必须按顺序输出(所以车厢 0,1,\cdots ,K−1 之中的最小值必须在车厢 1,2,\cdots ,K 之中的最小值之前输出,等等),但是除了这个顺序的限制之外,你的函数可以在任何一次函数调用中任意多次地输出一些最小值。比如,你的函数可能在某几次调用中不产生任何输出,而在某几次调用中产生多个输出。

Bessie 拥有惊人的短时记忆能力,因此在 helpBessie 函数中没有任何的内存使用限制,除了要满足常规的 256MB 限制。然而,在车厢与车厢之间,Bessie 不能够「记住」任何不在笔记本中出现过的内容。所以在两次函数调用之间,你的程序除了通过 getset 函数调用之外不能保存任何的状态。

这意味着:

**不允许定义任何非常量的全局或静态变量。任何如此做的提交会被取消成绩。教练会人工检查所有的提交以验证是否符合题目要求。由于这个问题无需文件输入输出,所以也不允许在代码中使用任何的文件输入输出。 **

样例

样例输入

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

样例输出

5
2
0
0
0
1
3
3

数据范围与提示

对于全部数据, 1\le N\le 10^6,0\le c_i\le 10^9,1\le K\le N ,你的程序进行的 set 调用和 get 调用的总次数被限制为 25\times 10^6 次。

Problem credits: Dhruv Rohatgi