记录编号	21481	评测结果	AAAAAAAAWA
题目名称	[POJ 2823]滑动窗口	最终得分	90
用户昵称	belong.zmx	是否通过	未通过
代码语言	Pascal	运行时间	3.121 s
提交时间	2010-11-11 07:42:44	内存使用	17.27 MiB

program windows(input,output);
var
 i,j:longint;
 a:array[0..1000000]of longint;
 f,g:array[0..1000000]of longint;
 f1,g1:array[0..1000000]of longint;
 n,k,p:longint;

begin
 assign(input,'window.in');
 reset(input);
 readln(n,k);
 for i:=1 to n do read(a[i]);
 close(input);

 a[0]:=maxlongint;
 for i:=2 to n do
 begin
  p:=i-1;
  if a[i]=a[p] then
  begin
   f[i]:=f[p];
   continue;
  end;
  if a[i]<a[p] then
  begin
   f[i]:=p;
   continue;
  end;
  while a[p]<a[i] do p:=f[p];
  if a[p]=a[i] then
  begin
   f[i]:=f[p];
   continue;
  end;
  if a[p]>a[i] then f[i]:=p;
 end;

 a[0]:=-maxlongint;
 for i:=2 to n do
 begin
  p:=i-1;
  if a[i]=a[p] then
  begin
   g[i]:=g[p];
   continue;
  end;
  if a[i]>a[p] then
  begin
   g[i]:=p;
   continue;
  end;
  while a[p]>a[i] do p:=g[p];
  if a[p]=a[i] then
  begin
   g[i]:=g[p];
   continue;
  end;
  if a[p]<a[i] then g[i]:=p;
 end;

 for i:=k to n do
 begin
  p:=i;
  while (f[p]<>0)and(f[p]>=i-k+1) do p:=f[p];
  f1[i-k+1]:=a[p];
  p:=i;
  while (g[p]<>0)and(g[p]>=i-k+1) do p:=g[p];
  g1[i-k+1]:=a[p];
 end;

 assign(output,'window.out');
 rewrite(output);
 for i:=1 to n-k do write(g1[i],' ');
 writeln(g1[i+1]);
 for i:=1 to n-k do write(f1[i],' ');
 writeln(f1[i+1]);
 close(output);
end.