Cod sursa(job #324949)

Utilizator ZillaMathe Bogdan Zilla Data 18 iunie 2009 06:45:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>

#define Nmax 500100

int st,vf,n,k,min,poz1=1,poz2;
char c;
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",&n,&k);
    for(i=1;i<=k;++i)
        {
            x=0;
            char neg=0;
            c=fgetc(stdin);
            if(c=='-')
                neg=1,
                c=fgetc(stdin);
            while(c>='0' && c<='9')
                {
                    x=x*10+(c-'0');
                    c=fgetc(stdin);
                }
             if(neg)
                x=x*(-1);
            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;
            x=0;
            char neg=0;
            c=fgetc(stdin);
            if(c=='-')
                neg=1,
                c=fgetc(stdin);
            while(c>='0' && c<='9')
                {
                    x=x*10+(c-'0');
                    c=fgetc(stdin);
                }
            if(neg)
                x=x*(-1);
            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;    
}