Cod sursa(job #286627)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 23 martie 2009 22:57:22
Problema Secventa Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.31 kb
// Arhiva de probleme - Deque
// Pascal = shit, pierde prea mult timp la citire.

var
        n, k, i, p, u, pp,uu,m   : longint;
        a, d            : array[1..500000] of longint;
        b               : array[1..5000000] of char;
        s               : longint;
        f               : text;

begin
assign  (f, 'secventa.in');
reset   (f);
readln  (f, n, k);
read    (f, b);
close   (f);

i:=1; n := 0;
while (b[i] <> #0) do
    begin
    inc(n);
    a[n] := 0; m:=1;
    if (b[i] = #45) then
        begin
        m := -1;
        inc(i);
        end;
    while (b[i] <> #0) and (b[i]<>#32) do
        begin
        a[n]:=a[n]*10+ord(b[i])-48;
        inc(i);
        end;
    a[n] := m * a[n];
    inc(i);
    end;


s       := -40000;
d[1]    := 1;
p       := 1;
u       := 1;

if (k=1) then begin s:=a[1]; uu := 1; end;

for i := 2 to n do
    begin
    // sterge elementele mai mari din coada
    while (p<=u) and (a[i] <= a[d[u]]) do
        u := u - 1;

    u := u + 1;
    d[u] := i;

    if (i - d[p] >= k)  then
        p := p + 1;

    if (i>=k) and (s < a[d[p]]) then
        begin
        s :=  a[d[p]];
        uu := i;
        end;



   end;

assign  (f, 'secventa.out');
rewrite (f);
writeln (f, uu-k+1,' ', uu, ' ', s);
close   (f);

end.