Cod sursa(job #849805)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 7 ianuarie 2013 17:47:20
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k,x,v[500005],maxi,nr,ok;
deque <int> d;

int main()
{
    int i;
    //g<<"Am inceput\n";
    f>>n>>k;
    //g<<i<<' '<<n<<' '<<k<<'\n';
    for(i=1;i<k;++i)
    {
        f>>x;
        v[i]=x;
        g<<x<<' ';
        ok=1;
        while(!d.empty()&&ok)
        {
            if(x<d.back()) d.pop_back();
            else ok=0;
        }
        d.push_back(x);
    }
    maxi=-30005;
    v[0]=v[1]+1;
    for(;i<=n;++i)
    {
        f>>x;
        if(v[i-k]==d.front()&&!d.empty()) d.pop_front();
        v[i]=x;
        while(x<d.back()&&!d.empty()) d.pop_back();
        d.push_back(x);
        if(d.front()>maxi)
        {
            maxi=d.front();
            nr=i-k+1;
        }
    }
    g<<nr<<' '<<nr+k<<' '<<maxi<<'\n';
    f.close(); g.close();
    return 0;
}