Cod sursa(job #1277183)

Utilizator Yasin_ibraimIbraim Yasin Yasin_ibraim Data 27 noiembrie 2014 12:12:19
Problema Text Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>

typedef struct deque
{
    int n,p;
}deque;

deque d[500002];
int v[500002];
char sir[5000000];

int main()
{
    FILE *f=freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,a,i,j,s=-2000000000,p1=1,p2=1,semn=0;
    scanf("%d%d\n",&n,&k);

    fgets(sir,5000000,f);
    i=0;j=1;
    while(sir[i]!='\n')
    {
        if(sir[i]==' ')
            ++i;
        if(sir[i]=='-')
        {
            semn=1;
            ++i;
        }
        while(sir[i]>='0'&&sir[i]<='9')
        {
            v[j]=v[j]*10+sir[i]-'0';
            ++i;
        }
        if(semn)
        {
            v[j]=-v[j];
            semn=0;
        }
        ++j;
    }
    i=1;j=0;
    d[0].n=-200000000;

    for(a=1;a<k;++a)
    {
        while(d[j].n>=v[a]&&j>=i)
            --j;
        ++j;
        d[j].n=v[a];
        d[j].p=a;
    }
    for(a=k;a<=n;++a)
    {
        while(d[i].p<=a-k&&i<=j)
            ++i;
        while(d[j].n>=v[a]&&j>=i)
            --j;
        ++j;
        d[j].n=v[a];
        d[j].p=a;
        if(d[i].n>s)
        {
            p1=a-k+1;
            s=d[i].n;
        }
    }
    p2=p1+k-1;
    printf("%d %d %d\n",p1,p2,s);
    return 0;
}