记录编号	23958	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	2.583 s
提交时间	2011-03-25 09:18:37	内存使用	17.28 MiB

var
  n,k,i,h,t,p:longint;
  q,a:array[0..2000000]of longint;
  f:array[0..2000000]of boolean;

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]);

  for i:=1 to n do f[i]:=false;

  q[1]:=a[1];
  h:=1;
  t:=1;
  f[1]:=true;

  for i:=2 to n do
  begin
    p:=t;

    while (a[i]<q[p])and(p>=h) do
    begin
      f[p]:=false;
      dec(p);
    end;

    if p<h then
    begin
      h:=i;
      t:=i;
    end;

    f[i]:=true;
    q[i]:=a[i];

    t:=i;
    while t-h+1>k do inc(h);
    while not f[h] do inc(h);
    if t>=k then write(q[h],' ');
    if t-h+1>=k then inc(h);
  end;

  for i:=1 to n do f[i]:=false;

  q[1]:=a[1];
  h:=1;
  t:=1;
  f[1]:=true;
  writeln;
  for i:=2 to n do
  begin
    p:=t;

    while (a[i]>q[p])and(p>=h) do
    begin
      f[p]:=false;
      dec(p);
    end;

    if p<h then
    begin
      h:=i;
      t:=i;
    end;

    f[i]:=true;
    q[i]:=a[i];

    t:=i;
    while t-h+1>k do inc(h);
    while not f[h] do inc(h);
    if t>=k then write(q[h],' ');
    if t-h+1>=k then inc(h);
  end;
  close(input);
  close(output);
end.