MINK - Huyền thoại Lục Vân Tiên

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

Const	fi		=	'';
		fo		=	'';
        maxn	=	20000;
Var		f,f2	:	text;
		a,r,l,s	:	array[0..maxn]of longint;
        n,k		:	longint;
Procedure openf;
   begin
     assign(f,fi); reset(f);
     assign(f2,fo); rewrite(f2);
   end;
Procedure closef;
   begin
     close(f); close(f2);
   end;
Procedure inp;
   var i:longint;
   begin
     readln(f,n,k);
     for i:=1 to n do read(f,a[i]);
     fillchar(l,sizeof(l),0);
     fillchar(r,sizeof(r),0);
     readln(f);
   end;
Procedure solve;
   var i,j,last:longint;
   begin
     fillchar(s,sizeof(s),0); last:=0;
     a[0]:=maxlongint; a[n+1]:=maxlongint;
     for i:=1 to n do
       begin
         while (last>0) and (a[i]<=a[s[last]]) do dec(last);
         l[i]:=s[last]+1;
         inc(last); s[last]:=i;
       end;
     fillchar(s,sizeof(s),0); last:=0; s[0]:=n+1;
     for i:=n downto 1 do
       begin
         while (last>0) and (a[i]<=a[s[last]]) do dec(last);
         r[i]:=s[last]-1;
         inc(last); s[last]:=i;
       end;
   end;
Procedure Out;
   var i,j:longint;
   begin
     j:=1;
     for i:=1 to n-k+1 do
       begin
         while not ((l[j]<=i) and (r[j]>=i+k-1) and (j>=i)) do inc(j);
         write(f2,a[j],' ');
       end;
     writeln(f2);
   end;
Procedure process;
   var i,t:longint;
   begin
     readln(f,t);
     for i:=1 to t do
       begin
         inp;
         solve;
         Out;
       end;
   end;
Begin
  openf;
  process;
  closef;
End.

Download