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

program w;
var
  qminhead,qmintail,qmaxhead,qmaxtail,i,j,n,k:longint;
  pqmin,pqmax,qmin,qmax,min,max,data:array [0..1000000] of longint;
procedure add;
begin
    if data[i]>qmin[qmintail] then begin
	  inc(qmintail);
	  qmin[qmintail]:=data[i];
	  pqmin[qmintail]:=i;
	end
	else begin
	  while (qmin[qmintail]>data[i]) and (qminhead<=qmintail) do dec(qmintail);
	  if qminhead>qmintail then qmintail:=qminhead else inc(qmintail);
	  qmin[qmintail]:=data[i];
	  pqmin[qmintail]:=i;
	end;
	if data[i]<qmax[qmaxtail] then begin
          inc (qmaxtail);
          qmax[qmaxtail]:=data[i];
	  pqmax[qmaxtail]:=i;
	end
	else begin
	  while (qmax[qmaxtail]<data[i]) and (qmaxhead<=qmaxtail) do dec(qmaxtail);
	  if qmaxhead>qmaxtail then qmaxtail:=qmaxhead else inc(qmaxtail);
	  qmax[qmaxtail]:=data[i];
	  pqmax[qmaxtail]:=i;
	end;
end;
begin
  assign (input,'window.in');
  reset (input);
  readln (n,k);
  fillchar (data,sizeof(data),0);
  fillchar (qmin,sizeof(qmin),0);
  fillchar (qmax,sizeof(qmax),0);
  fillchar (pqmin,sizeof(pqmin),0);
  fillchar (pqmax,sizeof(pqmax),0);
  for i:=1 to n do read (data[i]);
  close (input);
  assign (output,'window.out');
  rewrite (output);
  qminhead:=1;qmintail:=1;
  qmaxhead:=1;qmaxtail:=1;
  qmin[1]:=data[1];qmax[1]:=data[1];
  pqmin[1]:=1;pqmax[1]:=1;
  for i:=2 to k do add;
  min[0]:=qmin[qminhead];
  max[0]:=qmax[qmaxhead];
  for i:=k+1 to n do begin
    while (pqmin[qminhead]<=i-k) and (qminhead<=qmintail) do inc(qminhead);
	while (pqmax[qmaxhead]<=i-k) and (qmaxhead<=qmaxtail) do inc(qmaxhead);
        if qminhead>qmintail then begin
          qminhead:=qmintail;
          qmin[qminhead]:=-maxlongint;
        end;
        if qmaxhead>qmaxtail then begin
          qmaxhead:=qmaxtail;
          qmax[qmaxhead]:=maxlongint;
        end;
	add;
	min[i-k]:=qmin[qminhead];
	max[i-k]:=qmax[qmaxhead];
  end;
  write (min[0]);
  for i:=1 to n-k do write (' ',min[i]);
  writeln;
  write (max[0]);
  for i:=1 to n-k do write (' ',max[i]);
  writeln;
  close (output);
end.