Cod sursa(job #893161)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 26 februarie 2013 13:31:12
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <deque>

using namespace std;

int n, k, a[500010], start, minim;
deque <int> d;

int main()
{
    ifstream f ("secventa.in");
    f>>n>>k;
    int i;
    for (i=1; i<=n; i++)
        f>>a[i];
    f.close();

    for (i=1; i<=n; i++)
    {
        while (!d.empty() && a[i] <= a[d.back()])
            d.pop_back();
        d.push_back(i);
        if (d.front() == i-k)
            d.pop_front();
        if (i>=k)
        {
            if (a[d.front()] > minim)
            {
                minim = a[d.front()];
                start = i-k+1;
            }
        }
    }

    ofstream g("secventa.out");
    int sfarsit;
    sfarsit = start+k-1;
    while (start > 1 && a[start-1] >= minim)
        start--;
    g<<start<<" "<<sfarsit<<" "<<minim<<"\n";
    g.close();

    return 0;
}