Cod sursa(job #149792)

Utilizator marius21Marius Petcu marius21 Data 6 martie 2008 08:10:25
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.42 kb
var a,c,t,d:array[1..500000] of longint;
b:array[1..500000] of boolean;
k,n,i,poz,max,min,p:longint;
f,g:text;

procedure merge(si,sj:longint);
var nr,di,dj,i,j,m:longint;
begin
 if si<sj then begin
  m:=(si+sj)div 2;
  merge(si,m);
  merge(m+1,si);
  i:=si;
  j:=m+1;
  nr:=0;
  while (i<=m) and (j<=sj) do
   if a[c[i]]<=a[c[j]] then begin
    inc(nr);
    t[nr]:=c[i];
    inc(i);
    end else begin
    inc(nr);
    t[nr]:=c[j];
    inc(j);
    end;
  while (i<=m) do begin
   inc(nr);
   t[nr]:=c[i];
   inc(i);
   end;
  while (j<=sj) do begin
   inc(nr);
   t[nr]:=c[j];
   inc(j);
   end;
  for i:=1 to nr do
   c[si+i-1]:=t[i];
  end;
 end;

begin
assign(f,'secventa.in');
assign(g,'secventa.out');
reset(f);
rewrite(g);
read(f,n,k);
for i:=1 to n do begin
 read(f,a[i]);
 c[i]:=i;
 end;
{c[i]= al i-lea element din a in ordine cresc}
{b[i]= utilizat a[i]}
{d[i]= poz elementului a[i] in vector ordonat}
merge(1,n);
for i:=1 to n do
   d[c[i]]:=i;
poz:=d[1];
for i:=1 to k do begin
   b[d[i]]:=true;
   if d[i]<poz then
    poz:=d[i];
   end;
if a[c[poz]]>max then begin
  p:=1;
  max:=a[c[poz]];
  end;
for i:=k+1 to n do begin
 b[d[i-k]]:=false;
 while b[poz]=false do
   inc(poz);
 b[d[i]]:=true;
 if d[i]<poz then
  poz:=d[i];
 if a[c[poz]]>max then begin
  p:=i-k+1;
  max:=a[c[poz]];
  end;
 end;
writeln(g,p,' ',p+k-1,' ',max);
close(f);
close(g);
end.