Cod sursa(job #324943)

Utilizator ZillaMathe Bogdan Zilla Data 18 iunie 2009 06:16:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>

#define Nmax 500100

int st,vf,n,k,min,poz1=1,poz2;
struct stiva{
    int val,ind;
};

stiva s[Nmax];

int main()
{
    int i,x;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=k;++i)
        {
            scanf("%d",&x);
            while(vf>st && s[vf].val>=x)
                --vf;
            s[++vf].val=x;
            s[vf].ind=i;
        }
    min=s[1].val;
    poz2=k;
    for(i=k+1;i<=n;++i)
        {
            while(s[st+1].ind<i-k+1 && st<vf)
                ++st;
            scanf("%d",&x);
            while(vf>st && s[vf].val>=x)
                --vf;
            s[++vf].val=x;
            s[vf].ind=i;
            if(s[st+1].val>min)
                {
                    min=s[st+1].val;
                    poz1=i-k+1;
                    poz2=i;
                }
        }
    printf("%d %d %d",poz1,poz2,min);
    return 0;    
}