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

program dfjgd;
var n,k,i,j,l,h1,h2,t1,t2:longint;
    q1,q2:array[0..500000]of longint;
    a,max,min:array[1..1000000]of longint;
begin
assign(input,'window.in');
reset(input);
assign(output,'window.out');
rewrite(output);
{-----------------------------------------------}{in}
readln(n,k);
for i:=1 to n do
    read(a[i]);
{-----------------------------------------------}{min[1],min[2]}
h1:=1;
t1:=1;
h2:=1;
t2:=1;
q1[1]:=1;
q2[1]:=1;
for i:=2 to k do
begin
    while(q1[h1]<=i-k)and(h1<=t1)do
      inc(h1);
    while(q2[h2]<=i-k)and(h2<=t2)do
      inc(h2);
    while(a[q1[t1]]>=a[i])and(t1>=h1)do
      dec(t1);
    inc(t1);
    q1[t1]:=i;
    while(a[q2[t2]]<=a[i])and(t2>=h2)do
      dec(t2);
    inc(t2);
    q2[t2]:=i;
end;
min[1]:=a[q1[h1]];
max[1]:=a[q2[h2]];
{-----------------------------------------------}{min,max}
for i:=k+1 to n do
begin
    while(q1[h1]<=i-k)and(h1<=t1)do
      inc(h1);
    while(q2[h2]<=i-k)and(h2<=t2)do
      inc(h2);
    while(a[q1[t1]]>=a[i])and(t1>=h1)do
      dec(t1);
    inc(t1);
    q1[t1]:=i;
    while(a[q2[t2]]<=a[i])and(t2>=h2)do
      dec(t2);
    inc(t2);
    q2[t2]:=i;
    min[i-k+1]:=a[q1[h1]];
    max[i-k+1]:=a[q2[h2]];
end;
{-----------------------------------------------}{out}
for i:=1 to n-k do
    write(min[i],' ');
writeln(min[n-k+1]);
for i:=1 to n-k do
    write(max[i],' ');
writeln(max[n-k+1]);
close(input);
close(output);
end.