Cod sursa(job #1751785)

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

using namespace std;

int v[500005];

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;
    int deq[500010];
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%d",v+i);

    p=1;u=0;

    for(i=1;i<=k;i++)
    {
        a=v[i];
        while(p<=u&&v[deq[u]]>a)
            u--;
        deq[++u]=i;
    }

    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=deq[p]; // 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;
}