Cod sursa(job #1003340)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 30 septembrie 2013 14:54:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <cstring>
#include <deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n,k,bestbase;
int v[500001];

deque <int> d;

int main()
{
    fin>>n>>k;

    for (int i=1; i<=n; ++i) fin>>v[i];

int i=1;

   for (; i<=k; ++i)
    {
        while (!d.empty() && v[i] < v[d.back()]) d.pop_back();
        d.push_back(i);
    }

    v[0] = -30001;

    for (i=k+1; i<=n; ++i)
    {
        while (!d.empty() && v[i] < v[d.back()]) d.pop_back();
        d.push_back (i);

        if (i - d.front() + 1 > k) d.pop_front ();

        if (v[d.front()] > v[bestbase]) bestbase = d.front();
    }

    for (int i=bestbase; i>=1; --i)
    {
        if (v[i] < v[bestbase])
        {
            fout<<i+1<<" "<<i+k<<" "<<v[bestbase];
            return 0;
        }
    }
    fout <<1<<" "<<k<<" "<<v[bestbase];

}