记录编号	21604	评测结果	AAAAAAAAWA
题目名称	495.[POJ 2823]滑动窗口	最终得分	90
用户昵称	Des.	是否通过	未通过
代码语言	Pascal	运行时间	2.226 s
提交时间	2010-11-11 21:18:40	内存使用	20.71 MiB

program window;
var min,max:array[1..1000000,1..2]of longint;
    mini,minj,maxi,maxj,t,k,m,n,i,j,p:longint;
    ans1,ans2:array[1..1000000]of longint;
begin
assign(input,'window.in');
reset(input);
assign(output,'window.out');
rewrite(output);
readln(n,k);
read(i);
max[1,1]:=i;
min[1,1]:=i;
max[1,2]:=1;
min[1,2]:=1;
maxi:=1;
mini:=1;
maxj:=1;
minj:=1;
for t:=2 to n do
  begin
    read(i);
    if min[mini,1]>=i then
      begin
        inc(minj);
        mini:=minj;
        min[mini,1]:=i;
        min[mini,2]:=t;
      end
    else
      begin
        inc(minj);
        min[minj,1]:=i;
        min[minj,2]:=t;
      end;
    if max[maxi,1]<=i then
      begin
        inc(maxj);
        maxi:=maxj;
        max[maxi,1]:=i;
        max[maxi,2]:=t;
      end
    else
      begin
        inc(maxj);
        max[maxj,1]:=i;
        max[maxj,2]:=t;
      end;
    while (i<=min[minj-1,1])and(minj>mini) do dec(minj);
    while (i>=max[maxj-1,1])and(maxj>maxi) do dec(maxj);
    min[minj,1]:=i;
    min[minj,2]:=t;
    max[maxj,1]:=i;
    max[maxj,2]:=t;
    if min[mini,2]<=t-k then
      inc(mini);
    if max[maxi,2]<=t-k then
      inc(maxi);
    if t>=k then
      begin
        inc(p);
        ans1[p]:=min[mini,1];
        ans2[p]:=max[maxi,1];
      end;
  end;
for t:=1 to p do
  write(ans1[t],' ');
writeln;
for t:=1 to p do
  write(ans2[t],' ');
close(output);
end.