Cod sursa(job #84650)

Utilizator FoaiaFoaia de Hartie Foaia Data 16 septembrie 2007 11:18:37
Problema Secventa Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.87 kb
var a,q:array[1..500000] of longint;
    i,ic,d,r,poz,n,k,x,j:longint;
    f1,f2:text;
    ch:char;
    s:ansistring;
begin
        assign(f1,'secventa.in');
        reset(f1);
        assign(f2,'secventa.out');
        rewrite(f2);
        readln(f1,n,k);
        i:=1;
        readln(f1,s);
        x:=length(s);
        for j:=1 to x do
        begin
                if s[j]=' ' then
                begin
                        if ch='n' then a[i]:=a[i]*-1;
                        ch:='p';
                        inc(i)
                end
                else if s[j]='-' then ch:='n'
                              else a[i]:=a[i]*10+ord(s[j])-48;
        end;
        r:=-maxlongint;
        ic:=1;
        d:=0;
        for i:=1 to k-1 do
        begin
                if d>=ic then
                        while a[i]<=a[q[d]] do
                        begin
                                dec(d);
                                if d=ic-1 then break;
                        end;
                inc(d);
                q[d]:=i;
        end;
        for i:=k to n do
        begin
                if d>=ic then
                        while a[i]<=a[q[d]] do
                        begin
                                dec(d);
                                if d=ic-1 then break;
                        end;
                inc(d);
                q[d]:=i;
                if d>=ic then
                        while q[ic]<i-k+1 do
                        begin
                                inc(ic);
                                if d=ic-1 then break;
                        end;
                if a[q[ic]]>r then
                begin
                        r:=a[q[ic]];
                        poz:=i;
                end;
        end;
        write(f2,poz-k+1,' ',poz,' ',r);
        close(f1);
        close(f2);
end.