Cod sursa(job #598919)

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

using namespace std;

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

int main()
{
    ifstream fin ("secventa.in");
    ofstream fout ("secventa.out");
    fin >> N >> K;
    for (int i=1; i<=N; ++i)
    {
        fin >> X[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;
            }
        }
    }
    fout << Si-K+1 << " " << Si << " " << S << "\n";
    fin.close ();
    fout.close ();
    return 0;
}