Cod sursa(job #561658)

Utilizator acelasi7Tudor Maxim acelasi7 Data 20 martie 2011 23:16:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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);
    ifstream in("secventa.in");
    ofstream out("secventa.out");
    //scanf("%d%d",&n,&k);
    in>>n>>k;
    rt=0;
    lf=1;
    v[0]=minf;
    s=minf;
    for(i=1;i<=n;++i)
    {
        in>>v[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;
        }
    }
    out<<min<<" "<<max<<" "<<s<<'\n';
    //printf("%d %d %lld\n",min,max,s);
    return 0;
}