记录编号	466482	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	5.234 s
提交时间	2017-10-29 09:12:46	内存使用	232.99 MiB

#include<cstdio>
#include<cmath>
int n,k,arr[1000010],stbmx[1200010][25],stbmi[1200010][25];
int K2MnO4()
{
	for(int i=1;i<=n;i++)stbmx[i][0]=arr[i];
	for(int i=1;i<=n;i++)stbmi[i][0]=arr[i];
	return 0;
}
int MnO2()
{
	for(int j=1;j<log(n)/log(2);j++)
	for(int i=1;i<=n;i++)
	stbmx[i][j]=stbmx[i][j-1]>stbmx[i+(int)pow(2,j-1)][j-1]?stbmx[i][j-1]:stbmx[i+(int)pow(2,j-1)][j-1];
	return 0;
}
int O2()
{
	for(int j=1;j<=log(n)/log(2);j++)
	for(int i=1;i<=n;i++)
	stbmi[i][j]=stbmi[i][j-1]<stbmi[i+(int)pow(2,j-1)][j-1]?stbmi[i][j-1]:stbmi[i+(int)pow(2,j-1)][j-1];
	return 0;
}
int qrymx(int l,int r)
{
	int le=log(k)/log(2);
	int _=stbmx[l][le];
	int D=stbmx[r-(int)pow(2,le)+1][le];
	return _>D?_:D;
}
int qrymi(int l,int r)
{
	int le=log(k)/log(2);
	int _=stbmi[l][le];
	int D=stbmi[r-(int)pow(2,le)+1][le];
	return _<D?_:D;
}
int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
	int KMnO4=K2MnO4()+MnO2()+O2();
	for(int i=1;i<=n-k+1;i++)printf("%d ",qrymi(i,i+k-1));
	printf("\n");
	for(int i=1;i<=n-k+1;i++)printf("%d ",qrymx(i,i+k-1));
	return 0;
}