Cod sursa(job #561654)

Utilizator acelasi7Tudor Maxim acelasi7 Data 20 martie 2011 23:11:49
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<fstream>
#include<limits.h>
using namespace std;

#define minf INT_MIN

int deq[500002];
int v[500002];

int main()
{

    long long s=0;
    int n,k,i,lf,rt,min,max;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    scanf("%d%d",&n,&k);

    rt=0;
    lf=1;
    v[0]=minf;
    s=minf;
    for(i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
        while(lf<=rt&&v[deq[rt]]>v[i])
            --rt;
        deq[++rt]=i;
        if(deq[lf]==i-k)
            ++lf;
        if(i>=k&&v[deq[lf]]>s)
        {
            s=v[deq[lf]];
            min=i+1-k;
            max=i;
        }
    }
    printf("%d %d %lld\n",min,max,s);
    return 0;
}