记录编号	21504	评测结果	EEAAAAAATA
题目名称	[POJ 2823]滑动窗口	最终得分	70
用户昵称	donny	是否通过	未通过
代码语言	Pascal	运行时间	6.398 s
提交时间	2010-11-11 08:36:40	内存使用	39.74 MiB

program windows;
const
  two:array[1..21]of longint=(2,4,8,16,32,64,128,256,512,1048,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152);
type
  s=record
    max,min,l,r:longint;
  end;
var
  f:array[1..2097152]of s;
  i,j:longint;
  n,m,k,o,p,q:longint;
  s1,s2:array[1..1000000]of longint;
procedure fuck(const w,x,y:longint);
begin
  if f[x].max>f[y].max then f[w].max:=f[x].max
  else f[w].max:=f[y].max;
  if f[x].min<f[y].min then f[w].min:=f[x].min
  else f[w].min:=f[y].min;
  f[w].l:=f[x].l;
  f[w].r:=f[y].r;
end;
procedure go(const x,y:longint);
var
  i,j:longint;
begin
  for i:=1 to ((y-x+1) div 2) do
  begin
    j:=(x+((i-1)*2)) div 2;
    fuck(j,x+(i-1)*2,x+i*2-1);
  end;
  if x>2 then
  go(x div 2,x-1);
end;
procedure pan(const x:longint);
begin
  if (i<=f[x].l)and(j>=f[x].r) then
  begin
    if f[x].max>p then p:=f[x].max;
    if f[x].min<q then q:=f[x].min;
  end
  else
  begin
    if i<=f[x*2].r then
    begin
      pan(x*2);
      if j>=f[x*2+1].l then
        pan(x*2+1);
    end
    else
      if j>=f[x*2+1].l then
        pan(x*2+1);
  end;
end;
begin
  assign(input,'window.in');
  reset(input);
  assign(output,'window.out');
  rewrite(output);
  readln(n,k);
  for i:=1 to 21 do
    if n<=two[i] then
    begin
      m:=i+1;
      o:=two[i]-1;
      break;
    end;
  for i:=1 to n do
  begin
    read(f[o+i].max);
    f[o+i].min:=f[o+i].max;
    f[o+i].l:=i;
    f[o+i].r:=i;
  end;
  for i:=o+n+1 to two[m]-1 do
  begin
    f[i].min:=maxlongint;
    f[i].max:=-maxlongint;
    f[i].l:=i-o;
    f[i].r:=f[i].l;
  end;
  go(o+1,two[m]-1);
  i:=1;
  j:=k;
  while j<=n do
  begin
    p:=-maxlongint;
    q:=maxlongint;
    pan(1);
    s2[i]:=p;
    s1[i]:=q;
    inc(i);
    inc(j);
  end;
  for i:=1 to n-k do
    write(s1[i],' ');
  writeln(s1[n-k+1]);
  for i:=1 to n-k do
    write(s2[i],' ');
  writeln(s2[n-k+1]);
  close(input);
  close(output);
end.