Cod sursa(job #277622)

Utilizator andumMorie Daniel Alexandru andum Data 11 martie 2009 20:11:53
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

int n,k,p,u,a[500001],x,y,max=-20000000,d[500001],i;
char s[1000002];

void parsare()
{
     int i,j,c;
     
     fgets(s,500002,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);
    parsare();
    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]]>max) 
                           {
                            max=a[d[p]];
                            x=i-k+1;
                            y=i;
                           } 
        }
    printf("%d %d %d", x, y, max);
    return 0;
}