Cod sursa(job #290281)

Utilizator cristikIvan Cristian cristik Data 27 martie 2009 18:41:59
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>
#define max 500001
int a[max],deque[max],n,k,front,back,i,j=1,min=-300100,begin,end,minus;
char s[max*10];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    gets(s+1);
    for(i=1; i<=n; i++)
    {
        minus=0; a[i]=0;
        while(s[j]!='-' &&(s[j]<'0' || s[j]>'9')) j++;
        if(s[j]=='-') minus=1,j++;
        while(s[j]>='0' && s[j]<='9')
         a[i]=a[i]*10+(s[j]-'0'),j++;
        if(minus) a[i]=-a[i];
    }
    front=1; back=0;
    for(i=1; i<=n; i++)
    {
        while(front<=back && a[i]<=a[deque[back]]) back--;
        deque[++back]=i;
        if(deque[front]==i-k) front++;
        if(i>=k)
         if(min<a[deque[front]]) min=a[deque[front]],begin=i-k+1,end=i;
    }
    printf("%d %d %d",begin,end,min);
    return 0;
}