记录编号	21711	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	2.194 s
提交时间	2010-11-13 10:29:35	内存使用	7.75 MiB

{窗口
 单调队列
 Author：yangbohua
 Time：2010-11-13}

program window;
var
  a,q:array[0..1000000] of longint;
  n,k,i,t,h,p:longint;

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

  readln(n,k);
  for i:=1 to n do
    read(a[i]);

  t:=1;
  h:=1;
  q[1]:=a[1];
  for i:=2 to n do
  begin
    p:=h;
    while (a[i]>q[p]) and (p<=t) do
    begin
      p:=p+1;
    end;
    if p>t then
    begin
      t:=t+1;
      q[t]:=a[i];
    end
    else
    begin
      t:=p;
      q[t]:=a[i];
    end;
    if i>=k then
    begin
      write(q[h],' ');
      if a[i-k+1]=q[h]
        then h:=h+1;
    end;
  end;
  writeln;

  t:=1;
  h:=1;
  q[1]:=a[1];
  for i:=2 to n do
  begin
    p:=h;
    while (a[i]<q[p]) and (p<=t) do
    begin
      p:=p+1;
    end;
    if p>t then
    begin
      t:=t+1;
      q[t]:=a[i];
    end
    else
    begin
      t:=p;
      q[t]:=a[i];
    end;
    if i>=k then
    begin
      write(q[h],' ');
      if a[i-k+1]=q[h]
        then h:=h+1;
    end;
  end;
  writeln;

  close(input);
  close(output);
end.