Cod sursa(job #180287)

Utilizator savimSerban Andrei Stan savim Data 16 aprilie 2008 20:36:52
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#define maxl 500010

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

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

    val[0]=-30010;
    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;    
}