Cod sursa(job #1222039)

Utilizator PlatenitesVoicu Cristian Platenites Data 22 august 2014 00:25:13
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<cstdio>

using namespace std;

int v[500001],deq[500001],fr,b,n,k,maxi,dr,st;
int main ()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    maxi=-923123;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    fr=1;b=0;
    for(int i=1;i<=n;i++)
    {
        while(fr<=b && v[i]<=v[deq[b]])
            b--;
        deq[++b]=i;
        if(deq[fr]==i-k)
            fr++;
        if(i>=k && v[deq[fr]]>maxi)
        {
            maxi=v[deq[fr]];st=i-k+1;dr=i;
        }
    }
    printf("%d %d %d",st,dr,maxi);
}