Cod sursa(job #1257047)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 7 noiembrie 2014 10:07:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<deque>
#define NMAX 500010

using namespace std;

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

int n, k, a[NMAX];
deque<int> dq;

void citeste()
{
    f>>n>>k;
    for (int i=1; i<=n; ++i) f>>a[i];
}

void rezolva()
{
    int maxim=-30001, maximStart;

    for (int i=1; i<=n; ++i)
    {
        if (!dq.empty() && dq.front()==i-k) dq.pop_front();

        while (!dq.empty() && a[dq.back()]>=a[i]) dq.pop_back();
        dq.push_back(i);

        if (a[dq.front()]>maxim && i>=k)
        {
            maxim=a[dq.front()];
            maximStart=dq.front();
        }
    }

    g<<maximStart<<" "<<maximStart+k-1<<" "<<maxim<<"\n";
}


int main()
{
    citeste();
    rezolva();
    return 0;
}