记录编号	21502	评测结果	AAAAAAAAWA
题目名称	[POJ 2823]滑动窗口	最终得分	90
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	2.746 s
提交时间	2010-11-11 08:35:09	内存使用	20.70 MiB

program window(input,output);

type
  re=record
    dt,wh:longint;
  end;

var
  n,k,i,tmp,l,h1,h2,t1,t2:longint;
  a1,a2:array[0..1000001]of re;
  ans1,ans2:array[0..1000001]of longint;

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

  readln(n,k);

  read(tmp);
  a1[0].dt:=tmp;
  a2[0].dt:=tmp;
  a1[0].wh:=1;
  a2[0].wh:=1;
  for i:=2 to n do
  begin
    read(tmp);

    while (a1[h1].wh<=i-k)and(h1<=t1) do
      inc(h1);

    while (a2[h2].wh<=i-k)and(h1<=t1) do
      inc(h2);

    while (a1[t1].dt<tmp)and(h1<=t1) do
      dec(t1);

    while (a2[t2].dt>tmp)and(h2<=t2) do
      dec(t2);

    inc(t1);
    a1[t1].wh:=i;
    a1[t1].dt:=tmp;
    inc(t2);
    a2[t2].wh:=i;
    a2[t2].dt:=tmp;

    if i-k>=0 then
    begin
      inc(l);
      ans1[l]:=a1[h1].dt;
      ans2[l]:=a2[h2].dt;
    end;
  end;

  for i:=1 to l do
    write(ans2[i],' ');
  writeln;

  for i:=1 to l do
    write(ans1[i],' ');
  writeln;

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