Cod sursa(job #1643)

Utilizator pocaituDavid si Goliat pocaitu Data 14 decembrie 2006 09:59:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
int long v[500010],st[500000],sf,inc,max,pp,poz[500000],n,k;
void insereaza_stiva(int x,int p)
{int long i;
for(i=inc;st[i]>=x&&i<=sf;i++);
inc=i-1;
st[i-1]=x;
poz[i-1]=p;
}

int main()
{freopen("secventa.in","r",stdin);
 scanf("%ld%ld",&n,&k);
  int long i;
  for(i=1;i<=n;i++)
	scanf("%ld",&v[i]);
 //st[1]=v[1];poz[1]=1;inc=sf=1;
 poz[500000]=1,inc=sf=500000,st[inc]=v[1];
 for(i=1;i<=k;i++)
   insereaza_stiva(v[i],i);
 while(poz[inc]<=n)
 {//if(poz[inc]>n)
   //	break;

 if(st[sf]>max)
   {//pp- pozitia de inceput
	pp=poz[inc]-k+1;
	max=st[sf];
	}
	sf--;
	 if(k+poz[sf+1]>n)
	break;
  for(i=poz[inc]+1;i<=n&&i<=poz[sf+1]+k;i++)
	insereaza_stiva(v[i],i);

  }
 freopen("secventa.out","w",stdout);
  printf("%ld ",pp);
   printf("%ld ",pp+k-1);
  printf("%ld\n",max);
//  for(i=pp;i<=pp+k-1;i++)
 //	printf("%ld ",v[i]);
 fclose(stdout);
 return 0;
 }