Cod sursa(job #1751817)

Utilizator AlexVolatiluVoicu Alex AlexVolatilu Data 1 septembrie 2016 23:12:14
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>

using namespace std;

int v[500005];
int deq[500005];
char buff[1000005];
int lung=1,pozbuff;

int read()
{
    int x=0,sgn=1;
    while((buff[pozbuff]<'0'||buff[pozbuff]>'9')&&buff[pozbuff]!='-')
    {
        if(++pozbuff==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            pozbuff=0;
        }

    }
    if(buff[pozbuff]=='-'){sgn=-1;pozbuff++;}
    if(pozbuff==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            pozbuff=0;
        }
    while((buff[pozbuff]>='0'&&buff[pozbuff]<='9')||buff[pozbuff]=='-')
    {
         x=x*10+buff[pozbuff]-'0';
        if(++pozbuff==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            pozbuff=0;
        }
    }
    return x*sgn;

}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,i,p,u,a,poz,len,m=-1000000,deltapoz,pozfin;
    n=read();
    k=read();
    for(i=1;i<=n;i++)
        v[i]=read();

    p=1;u=0;

    for(i=1;i<=k;i++)
    {
        a=v[i];
        while(p<=u&&v[deq[u]]>a)
            u--;
        deq[++u]=i;
    }
    if(m<v[deq[p]])
    {
        m=v[deq[p]];
        poz=i; // i sau deq[p]
    }
    for(i=k+1;i<=n;i++)
    {
        a=v[i];
        while(p<=u&&v[deq[u]]>a)
            u--;
        deq[++u]=i;
        if(i-deq[p]>=k) p++;
        if(m<v[deq[p]])
        {
            m=v[deq[p]];
            poz=i; // i sau deq[p]
        }
    }

   /* for(i=poz-1;v[i]>m;i--);

    deltapoz=poz-i;
    if(k<deltapoz) pozfin=poz;
    else pozfin=poz+k-deltapoz;
    printf("%d %d %d",i+1,pozfin,m);*/
    printf("%d %d %d",poz-k+1,poz,m);

    return 0;
}