Cod sursa(job #346673)

Utilizator ionutz32Ilie Ionut ionutz32 Data 8 septembrie 2009 23:36:51
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#define NMAX 500000
using namespace std;
int v[NMAX],dq[NMAX],n,k,i,lo,hi,max,poz;
int main()
{
    ifstream f;
    ofstream g;
    f.open("secventa.in");
    g.open("secventa.out");
    f>>n>>k;
    for (i=1;i<=n;++i)
        f>>v[i];
    lo=1;hi=0;max=-30001;
    for (i=1;i<=n;++i)
    {
        while (lo<=hi && v[dq[hi]]>=v[i])
              --hi;
        ++hi;
        dq[hi]=i;
        if (i>=k)
        {
           if (dq[lo]==i-k)
              ++lo;
           if (v[dq[lo]]>max)
           {
              max=v[dq[lo]];
              poz=i;
           }
        }
    }
    g<<poz-k+1<<" "<<poz<<" "<<max;
    f.close();
    g.close();
    return 0;
}