Cod sursa(job #289389)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 26 martie 2009 18:39:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>  
long n,k,p,u;  
char s[3500010];  
long v[500010];  
long deq[500010];  
  
void read()  
{  
    freopen("secventa.in","r",stdin);  
    freopen("secventa.out","w",stdout);  
    scanf("%ld%ld\n",&n,&k);  
    n=0;  
    gets(s);  
    int semn=1,i;  
    long val=0;  
    for(i=0;s[i];i++)  
    {  
        if(s[i]=='-')  
        {  
            semn=-1;  
            continue;  
        }  
        if(s[i]>='0' && s[i]<='9')  
        {  
            val=val*10+(s[i]-'0');  
            continue;  
        }  
        v[++n]=semn*val;  
        semn=1;  
        val=0;  
    }  
    if(s[i-1]!=' ')  
    {  
        v[++n]=semn*val;  
    }  
}  
  
void adauga(long i)  
{  
    while(u>p && v[deq[u]]>=v[i])  
        u--;  
    deq[++u]=i;  
}  
  
void rez()  
{  
    long i,cu=k,cp=1,max=-32001;  
    p=1;  
    u=0;  
    for(i=1;i<=k;i++)  
    {  
        adauga(i);  
    }  
    for(i=k+1;i<=n;i++)  
    {  
        if(deq[p]==i-k)  
            p++;  
		adauga(i);
        if(v[deq[p]]>max)  
        {  
            cp=deq[p];  
            cu=deq[u];  
            max=v[deq[p]];  
        }  
    }  
    printf("%ld %ld %ld\n",cp,cu,max);  
}  
  
int main()  
{  
    read();  
    rez();  
    return 0;  
}