单调队列= =

yuebaosanqing

var
a:array[1..2000000] of longint;
max,min:array[1..2000000,1..2] of longint;
answer1,answer2:array[1..2000000] of longint;
n,m,i,j,k,p,head1,tail1,head2,tail2:longint;
flag:boolean;
procedure insert1(x,time:longint);
var
l,r,mid:longint;
begin
        l:=head1;
        r:=tail1;
        if l=r then begin
        if x>=max[l,1] then begin
        tail1:=l; max[l,1]:=x; max[l,2]:=time; end
        else begin
        inc(tail1);
        max[tail1,1]:=x;
        max[tail1,2]:=time;
        end;
        end
        else begin
        while l+1<r do
        begin
        mid:=(l+r) div 2;
        if x>=max[mid,1] then r:=mid
        else l:=mid;
        end;
        if x>=max[l,1] then begin
        tail1:=l; max[l,1]:=x; max[l,2]:=time; end
        else if x>=max[r,1] then  begin
        tail1:=r; max[r,1]:=x; max[r,2]:=time;
        end
        else begin
        inc(tail1);
        max[tail1,1]:=x;
        max[tail1,2]:=time;
        end;
        end;
end;

procedure insert2(x,time:longint);
var
l,r,mid:longint;
begin
        l:=head2;
        r:=tail2;
        if l=r then begin
        if x<=min[l,1] then begin
        tail2:=l; min[l,1]:=x; min[l,2]:=time; end
        else begin
        inc(tail2);
        min[tail2,1]:=x;
        min[tail2,2]:=time;
        end;
        end
        else begin
        while l+1<r do
        begin
        mid:=(l+r) div 2;
        if x<=min[mid,1] then r:=mid
        else l:=mid;
        end;
        if x<=min[l,1] then begin
        tail2:=l; min[l,1]:=x; min[l,2]:=time; end
        else if x<=min[r,1] then begin
        tail2:=r; min[r,1]:=x; min[r,2]:=time;
        end
        else begin
        inc(tail2);
        min[tail2,1]:=x;
        min[tail2,2]:=time;
        end;
        end;
end;


begin
        fillchar(max,sizeof(max),0);
        fillchar(min,sizeof(min),0);
        readln(n,k);
        head1:=1;
        head2:=1;
        tail1:=1;
        tail2:=1;
        for i:=1 to n do
                read(a[i]);
        max[tail1,1]:=a[1];
        min[tail2,1]:=a[1];
        max[tail1,2]:=1;
        min[tail2,2]:=1;
        for i:=2 to k do
        begin
                insert1(a[i],i);
                insert2(a[i],i);
        end;
        answer1[1]:=max[1,1];
        answer2[1]:=min[1,1];
        for i:=k+1 to n do
        begin
                flag:=false;
                for j:=head1 to tail1 do
                        if (i-max[j,2])<k
                        then begin flag:=true; break; end;
                if flag=true then begin
                head1:=j;  insert1(a[i],i); end
                else begin head1:=j+1; tail1:=head1;
                max[tail1,1]:=a[i]; max[tail1,2]:=i; end;
                flag:=false;
                for j:=head2 to tail2 do
                        if (i-min[j,2])<k
                        then begin flag:=true; break; end;
                if flag=true then begin
                head2:=j; insert2(a[i],i); end
                else begin head2:=j+1; tail2:=head2;
                min[tail2,1]:=a[i]; min[tail2,2]:=i; end;



                answer1[i-k+1]:=max[head1,1];
                answer2[i-k+1]:=min[head2,1];
        end;
          write(answer2[1]);
        for i:=2 to n-k+1 do
                write(' ',answer2[i]);
        writeln;
        write(answer1[1]);
        for i:=2 to n-k+1 do
                write(' ',answer1[i]);
        writeln;

end.

yuebaosanqing

好吧。最裸的

私货男Vsop

这是什么呢

TCMario

教程铁在哪里？

siai

围观、。、。

星皇、孤寂毁灭

什么
再次不明觉厉

龙

再次吐槽delphi的赋值和比较运算符看着别扭死了= =

鬼子

pascal= =目前我是被学校老师逼着学这个，明年要竞赛

幻夜星云

对pascal无感

yuebaosanqing

Coolness 发表于 2014-2-11 23:03
pascal= =目前我是被学校老师逼着学这个，明年要竞赛

NOIP还是NOI

yuebaosanqing

龙 发表于 2014-2-11 16:10
再次吐槽delphi的赋值和比较运算符看着别扭死了= =

鬼子

yuebaosanqing 发表于 2014-2-12 20:03
NOIP还是NOI

应该是NOI吧

yuebaosanqing

Coolness 发表于 2014-2-12 22:47
应该是NOI吧

表示虽然也要去NOI。。但感觉毫无前途啊

上邪

Coolness 发表于 2014-2-11 23:03
pascal= =目前我是被学校老师逼着学这个，明年要竞赛

你还好了。我们这里根本没条件竞赛

鬼子

yuebaosanqing 发表于 2014-2-13 09:02
表示虽然也要去NOI。。但感觉毫无前途啊

= = 我们学校的高考状元听老师吹得之牛逼了，竞赛1等奖 = =

yuebaosanqing

Coolness 发表于 2014-2-13 11:34
= = 我们学校的高考状元听老师吹得之牛逼了，竞赛1等奖 = =

金牌？

Rise

上邪 发表于 2014-2-13 09:18
你还好了。我们这里根本没条件竞赛

同→_→

Rise

上邪 发表于 2014-2-13 09:18
你还好了。我们这里根本没条件竞赛

我们只有主科的竞赛→_→

Rise

只见过优先队列→_→

鬼子

yuebaosanqing 发表于 2014-2-13 13:14
金牌？

貌似是这样

yuebaosanqing

Coolness 发表于 2014-2-13 22:09
貌似是这样

可怕

上邪

Liberty 发表于 2014-2-13 21:51
我们只有主科的竞赛→_→

→_→我们这里就语数英竞赛

Rise

上邪 发表于 2014-2-14 11:11
→_→我们这里就语数英竞赛

→_→差不多 我们还有化学

余音的犹存

恩啊