记录编号	350896	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.454 s
提交时间	2016-11-16 07:24:00	内存使用	91.75 MiB

#include <stdio.h>
#include <queue>

const size_t MAX_BUF = 80 * 1024 * 1024;
int read_len = 0;
char reader[MAX_BUF];

inline void Read(int &num) {
	num = 0; bool minus = false;
	while (reader[read_len] < '-' || reader[read_len] > '9') ++read_len;
	if (reader[read_len] == '-') { minus = true; ++read_len; }
	while (reader[read_len] >= '0' && reader[read_len] <= '9')
		num = num * 10 + reader[read_len++] - '0';
	if (minus) num = -num;
}

const size_t MAXN = 1000000 + 11;

int num[MAXN];
int vmax[MAXN], vmin[MAXN];
std::deque<int> Qmin, Qmax;

inline void Insert(const int &x) {
	// 维护单调性
	while (!Qmax.empty() && num[x] >= num[Qmax.back()]) Qmax.pop_back();
	Qmax.push_back(x);
	while (!Qmin.empty() && num[x] <= num[Qmin.back()]) Qmin.pop_back();
	Qmin.push_back(x);
}

#define SUBMIT

int main() {
 #ifdef SUBMIT
	freopen("window.in", "r", stdin);
	freopen("window.out", "w", stdout);
	fread(reader, 1, MAX_BUF, stdin);
 #endif

	int n, k; Read(n); Read(k);
	for (int i = 1; i <= n; ++i) Read(num[i]);
	for (int i = 1; i <= n; ++i) {
		Insert(i); if (i < k) continue;
		// 窗口中只能有k个元素，排除失效元素
		if (!Qmax.empty() && Qmax.front() < i - k + 1) Qmax.pop_front();
		if (!Qmin.empty() && Qmin.front() < i - k + 1) Qmin.pop_front();
		vmax[i] = num[Qmax.front()]; vmin[i] = num[Qmin.front()];
	}
	for (int i = k; i <= n; ++i) printf("%d ", vmin[i]);
	putchar('\n');
	for (int i = k; i <= n; ++i) printf("%d ", vmax[i]);

 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}