Cod sursa(job #598917)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 27 iunie 2011 15:56:49
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <deque>

using namespace std;

deque <int> D;
int N, K, X[500005], Baza, S=-100000, Si;

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", &X[i]);
    }
    for (int i=1; i<=N; ++i)
    {
        while (!D.empty () and X[D.back ()]>X[i])
        {
            D.pop_back ();
        }
        D.push_back (i);
        if (D.front ()<=i-K)
        {
            D.pop_front ();
        }
        if (i>=K)
        {
            Baza=X[D.front ()];
            if (Baza>S)
            {
                S=Baza;
                Si=i;
            }
        }
    }
    printf ("%d %d %d\n", Si-K+1, Si, S);
    return 0;
}