Cod sursa(job #1667808)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 29 martie 2016 11:39:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>

using namespace std;
int d[5000005],v[5000005];
char s[4000000];
int main()
{
    FILE *fin=fopen ("secventa.in","r");
    FILE *fout=fopen ("secventa.out","w");
    int n,k,i,p,u,maxi,pp,uu,semn,x,j;
    fscanf (fin,"%d%d\n",&n,&k);
    fgets (s,3600000,fin);
    i=0;
    semn=1;
    x=0;
    j=0;
    while (s[i]!=0 && s[i]!='\n'){
        if (s[i]>='0' && s[i]<='9')
            x=x*10+s[i]-'0';
        else if (s[i]=='-')
            semn=-1;
        else if (s[i]==' '){
            if (s[i-1]>='0' && s[i]<='9'){
                j++;
                v[j]=x*semn;
                semn=1;
                x=0;
            }
        }
        i++;
    }
    if (s[i]=='\n' && s[i-1]>='0' && s[i]<='9'){
        j++;
        v[j]=x*semn;
    }
    d[1]=1;
    p=pp=1;
    u=uu=1;
    maxi=v[d[1]];
    for (i=2;i<=n;i++){
        while (p<=u && v[i]<=v[d[u]])
            u--;
        u++;
        d[u]=i;
        if (i-d[p]==k)
            p++;
        if (i>=k){
            //printf ("%d ",v[d[p]]);
            if (v[d[p]]>maxi){
                maxi=v[d[p]];
                pp=i-k+1;
                uu=i;
            }
        }
    }
    fprintf (fout,"%d %d %d",pp,uu,maxi);
    return 0;
}