Cod sursa(job #160685)

Utilizator SILVER_BOY22Dalalau Alexandru SILVER_BOY22 Data 16 martie 2008 17:18:20
Problema Secventa Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.35 kb
var l,i,j,n,jmin,smin,rez,minus,k,sa,st,t,err:longint;
    v:array[1..500000]of integer;
    min:array[1..500000]of integer;
    s:array[1..1750000]of char;
    nr:string;
    x:ansistring;

begin
assign(input,'secventa.in');reset(input);
assign(output,'secventa.out');rewrite(output);
readln(n,k);
readln(s);
i:=1;
t:=0;
x:=s;
l:=length(x);
while i<=l do
        begin
        nr:='';
        minus:=1;
        inc(t);
        if s[i]='-' then
                begin
                minus:=-1;
                inc(i);
                end;
        while (s[i]<>' ')and(i<=l) do
                begin
                v[t]:=v[t]*10+ord(s[i])-48;
                inc(i);
                end;
        v[t]:=v[t]*minus;
        inc(i);
        end;
smin:=1;
min[1]:=v[1];
jmin:=1;
for i:=2 to k do
    begin
    while (min[smin]>v[i])and(smin>0) do
        dec(smin);
    inc(smin);
    min[smin]:=v[i];
    end;
rez:=-maxint;
if min[jmin]>rez then
        begin
        rez:=min[jmin];
        sa:=1;
        st:=k;
        end;
for i:=k+1 to n do
    begin
    while (min[smin]>v[i])and(smin>=jmin) do
        dec(smin);
    inc(smin);
    min[smin]:=v[i];
    if v[i-k]=min[jmin] then
       inc(jmin);
    if (min[jmin]>rez) then
        begin
        rez:=min[jmin];
        sa:=i-k+1;
        st:=i;
        end;
    end;
writeln(sa,' ',st,' ',rez);
close(input);close(output);
end.