Cod sursa(job #1003347)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 30 septembrie 2013 15:03:16
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cstring>
#include <deque>
#include <cstdio>

using namespace std;

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

deque <int> d;

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


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

    for (int i=1; i<=n; ++i) scanf ("%d",&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])
        {
            printf("%d %d %d",i+1,i+k,v[bestbase]);
            return 0;
        }
    }
    printf ("%d %d %d",1,k,v[bestbase]);

}