Cod sursa(job #263622)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 20 februarie 2009 18:16:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char v[4000001];
int n,k,i,a[500001],p[500001],st,dr,s,m;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d\n",&n,&k);
    st=1;dr=0;
    s=-2000000000;
    gets(v);
    a[1]=atoi(strtok(v," \n"));
    for(i=2;i<=n;i++)
                     a[i]=atoi(strtok(NULL," \n"));
    p[1]=1;
    dr=1;
    for(i=2;i<=n;i++)
    {
                     while(a[p[dr]]>a[i]&&dr>=st)
                                                 dr--;
                     p[++dr]=i;
                     if(i>=k)
                     {
                             if(p[st]<=i-k)
                                           st++;
                             if(a[p[st]]>s)
                             {             
                                           s=a[p[st]];
                                           m=i;
                             }
                     }
    }
    printf("%d %d %d\n",m-k+1,m,s);
    return 0;
}