Cod sursa(job #180296)

Utilizator savimSerban Andrei Stan savim Data 16 aprilie 2008 20:49:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#define maxl 500010
#include <string.h>

int i,j,k,n,l,r,max=-30010,p,q,semn;
int dec[maxl],val[maxl];
char s[4000010];

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    
    scanf("%d %d\n",&n,&k);l=k;
/*    for (i=1; i<=n; i++)
        scanf("%d ",&val[i]); */

    fgets(s,4000000,stdin);
    i=0;k=strlen(s)-1;q=0;
    while (i<k)
    {
        semn=1;p=0;
        if (s[i]=='-') { semn=-1;i++;}
        while (s[i]!=' ' && i<k)
        {
              p=p*10+s[i]-48;
              i++;      
        }
        i++;
        q++;
        val[q]=p*semn;
    }

    val[0]=-30010;k=l;
    for (i=1; i<=k; i++)
    {
        r++;
        dec[r]=i;
        while (val[dec[r-1]]>val[dec[r]])
        {
              dec[r-1]=dec[r];
              r--;      
        }
    }                        
    
    max=val[dec[1]];p=1;q=k;
    l=1;
    for (i=k+1; i<=n; i++)
    {
        if (dec[l]<=i-k) 
        {
            dec[l]=-30100;
            l++;
        }
        
        r++;
        dec[r]=i;
        
        while (r-1>=l && val[dec[r-1]]>val[dec[r]])
        {
              dec[r-1]=dec[r];
              r--;      
        }
        
        if (val[dec[l]]>max)
        {
           max=val[dec[l]];p=i-k+1;q=i;               
        }
    }    

    printf("%d %d %d\n",p,q,max);
    
    return 0;    
}