记录编号	210103	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	Pascal	运行时间	5.041 s
提交时间	2015-11-25 13:21:47	内存使用	84.09 MiB

program zht;
var
n,m,j,i,k,x,ans:longint;
a:array[0..1000000] of longint;
f:array[0..1000000,0..20] of longint;

function min(a,b:longint):longint;
begin
if a<=b then min:=a else min:=b;
end;

function max(a,b:longint):longint;
begin
if a>=b then max:=a else max:=b;
end;

begin
assign(input,'window.in');
assign(output,'window.out');
reset(input);
rewrite(output);

readln(n,k);
fillchar(f,sizeof(f),$7f);

for i:=1 to n do
begin
read(a[i]);
f[i,0]:=a[i];
end;

for j:=1 to trunc(ln(n)/ln(2)) do
 for i:=1 to n+1-(1 shl j) do
  f[i,j]:=min(f[i,j-1],f[i+1 shl (j-1),j-1]);

x:=trunc(ln(k)/ln(2));


for i:=1 to n-k+1 do
begin
ans:=min(f[i,x],f[i+k-(1 shl (x)),x]);
write(ans,' ');
end;
writeln;

fillchar(f,sizeof(f),0);

for i:=1 to n do
f[i,0]:=a[i];

for j:=1 to trunc(ln(n)/ln(2)) do
 for i:=1 to n+1-(1 shl j) do
  f[i,j]:=max(f[i,j-1],f[i+1 shl (j-1),j-1]);

for i:=1 to n-k+1 do
begin
ans:=max(f[i,x],f[i+k-(1 shl (x)),x]);
write(ans,' ');
end;
writeln;

close(input);
close(output);

end.