Cod sursa(job #198537)

Utilizator marius21Marius Petcu marius21 Data 12 iulie 2008 12:43:30
Problema Secventa Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.94 kb
{var n,k,fin,ini,pimax,i,max,pfmax:longint;
a,b:array[0..500001] of longint;
f,g:text;

function secv(i:longint; var pi,pf:longint):boolean;
begin
pi:=i;
pf:=i;
while (pf-pi+1<k) and (a[pi-1]>=a[i]) and (pi>1) do
	dec(pi);
while (pf-pi+1<k) and (a[pf+1]>=a[i]) and (pf<n) do
	inc(pf);
if pf-pi+1=k then
		secv:=true
else  secv:=false;
end;

begin
assign(f,'secventa.in');
assign(g,'secventa.out');
reset(f);
rewrite(g);
read(f,n,k);
max:=-maxlongint;
for i:=1 to n do read (f,a[i]);
for i:=1 to n do
	if a[i]>max then
		if secv(i,ini,fin) then begin
      	max:=a[i];
         pimax:=ini;
         pfmax:=fin;
         end;
writeln(g,pimax,' ',pfmax,' ',max);
close(f);
close(g);
end.}
{var n,k,i,st,en,nr:longint;
a,b,t:array[0..500001] of 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,sj);
  i:=si;
  j:=m+1;
  nr:=0;
  while (i<=m) and (j<=sj) do
   if a[b[i]]<=a[b[j]] then begin
    inc(nr);
    t[nr]:=b[i];
    inc(i);
    end else begin
    inc(nr);
    t[nr]:=b[j];
    inc(j);
    end;
  while (i<=m) do begin
   inc(nr);
   t[nr]:=b[i];
   inc(i);
   end;
  while (j<=sj) do begin
   inc(nr);
   t[nr]:=b[j];
   inc(j);
   end;
  for i:=1 to nr do
   b[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]);
  b[i]:=i;
  end;
merge(1,n);
for i:=n-k+1 downto 1 do begin
  nr:=1;
  st:=b[i]-1;
  while (st>=1) and (nr<k) and (a[st]>=a[b[i]]) do begin
    inc(nr);
    dec(st);
    end;
  en:=b[i]+1;
  while (en<=n) and (nr<k) and (a[en]>=a[b[i]]) do begin
    inc(nr);
    inc(en);
    end;
  if nr=k then break;
  end;
writeln(g,st+1,' ',en-1,' ',a[b[i]]);
close(f);
close(g);
end.
end.}

var n,k,maxp,minp,i,st,ln,stm,fim,nr:longint;
a,b,t:array[0..500001] of longint;
f,g:text;
begin
assign(f,'secventa.in');
assign(g,'secventa.out');
reset(f);
rewrite(g);
read(f,n,k);
for i:=1 to n do
  read(f,a[i]);
st:=1;
ln:=0;
a[0]:=-maxlongint;
maxp:=0;
minp:=1;
while st+ln-1<n do begin
  if a[ln+st]<a[maxp] then begin {cazul de saritura}
    st:=ln+st+1;
    ln:=0;
    minp:=st;
    end else
    begin {cazul de mers normal}
    if a[ln+st]<=a[minp] then
      minp:=ln+st;
    if ln=k then begin {cazul de lungime implinita}
      if minp=st then begin
        minp:=st+1;
        for i:=st+1 to st+ln do
          if a[i]<a[minp] then
            minp:=i;
        end;
      maxp:=minp;
      stm:=st+1;
      fim:=st+k;
      inc(st);
      end else
      begin {cazul de lungime neimplinita}
      if ln=k-1 then begin{cazul de lungime implinibila}
        maxp:=minp;
        stm:=st;
        fim:=st+k-1;
        end;
      inc(ln);
      end;
    end;
  end;
writeln(g,stm,' ',fim,' ',a[maxp]);
close(f);
close(g);
end.
end.