Cod sursa(job #266564)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 25 februarie 2009 20:01:46
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.94 kb
// Arhiva de probleme - Deque
// Pascal = shit, pierde prea mult timp la citire.

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

begin
assign  (f, 'secventa.in');
reset   (f);
readln  (f, n, k);
for i := 1 to n do
    read (f, a[i]);
close   (f);

s       := a[1];
d[1]    := 1;
p       := 1;
u       := 1; pp := 1; uu := k;
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 (d[p] <= i-k) then
        p := p + 1;
    if (i>=k) and (s < a[d[p]]) then
        begin
        s :=  a[d[p]];
        pp := i-k+1;  //important!
        uu := i;      //important!
        end;
    end;

assign  (f, 'secventa.out');
rewrite (f);
writeln (f, pp,' ', uu, ' ', s);
close   (f);

end.