Cod sursa(job #285869)

Utilizator lolopolololopolo lolopolo Data 23 martie 2009 09:00:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
 #include <stdio.h>
 #define N 500*1001
 #define M N*7

 int n,k,p,u,a[N],x,y,minb=-100000,d[N],i;
 char s[M];

 void cif()
 {
      int i,j,c;

     fgets(s,M,stdin);
      for(i=1,j=0;i<=n;i++)
	  {
	   while(s[j]==' ') j++;
	  if(s[j]=='-') { c=1; j++; }
	      else c=0;
	   while(s[j]>='0' && s[j]<='9') a[i]=a[i]*10+s[j++]-48;
	 if (c) a[i]*=-1;
	  }
 }

 int main()
 {
     freopen("secventa.in","r",stdin);
     freopen("secventa.out","w",stdout);
    scanf("%d %d\n", &n, &k);
     cif();
     p=1; u=0;
     for (i=1;i<=n;++i)
	 {
	  while (p<=u && a[i]<=a[d[u]])
		u--;
	  d[++u]=i;
	  if (d[p]==i-k) ++p;
	 if (i>=k)
	   if (a[d[p]]>minb)
			    {
			     minb=a[d[p]];
			     x=i-k+1;
			     y=i;
			    }
	}
     printf("%d %d %d", x, y, minb);
    return 0;
}