记录编号	409667	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	sakura	是否通过	通过
代码语言	C++	运行时间	2.809 s
提交时间	2017-05-28 20:41:56	内存使用	229.20 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
vector<int> amax,amin;
int mapa[1000005][30],mapb[1000005][30];
int n,k;
void work()
{
    int i,j;
    for(j=1;1<<j<=n;j++)
    for(i=1;i+(1<<j)-1<=n;i++)
    {
    mapa[i][j]=min(mapa[i][j-1],mapa[i+(1<<j-1)][j-1]);
	mapb[i][j]=max(mapb[i][j-1],mapb[i+(1<<j-1)][j-1]);
	}
}
void question(int z,int y)
{
    int x=int (log(y-z+1)/log(2));
    amin.push_back(min(mapa[z][x],mapa[y-(1<<x)+1][x]));
    amax.push_back(max(mapb[z][x],mapb[y-(1<<x)+1][x]));
}
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",&mapa[i][0]);
		mapb[i][0]=mapa[i][0];
	}
	work();
    for(int i=1;i+k-1<=n;i++)
        {
            question(i,i+k-1);
        }
    for(int i=0;i<amin.size();i++)
    printf("%d ",amin[i]);
    cout<<endl;
	for(int i=0;i<amax.size();i++)  
    printf("%d ",amax[i]);
}