Cod sursa(job #2044384)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 21 octombrie 2017 09:46:41
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <deque>

using namespace std;

FILE *fin=fopen("secventa.in","r");
ofstream fout("secventa.out");

struct elem
{
    int x, poz;
};

int n, k, maxim=-999999, pozMax;
elem v[500005];
deque<elem> d;

int main()
{
    int i;

    fscanf(fin,"%d%d",&n,&k);
    for (i=1;i<=k;i++)
    {
        fscanf(fin,"%d",&v[i].x);
        v[i].poz = i;
        while (!d.empty() && d.back().x >= v[i].x)
            d.pop_back();
        d.push_back(v[i]);
    }
    if (d.front().x > maxim)
    {
        maxim = d.front().x;
        pozMax = 1;
    }
    for (i=k+1;i<=n;i++)
    {
        if (d.front().poz < i-k+1)
            d.pop_front();
        fscanf(fin,"%d",&v[i].x);
        v[i].poz = i;
        while (!d.empty() && d.back().x >= v[i].x)
            d.pop_back();
        d.push_back(v[i]);
        if (d.front().x > maxim)
        {
            maxim = d.front().x;
            pozMax = i-k+1;
        }
    }
    fout << pozMax << ' ' << pozMax+k-1 << ' ' << maxim << '\n';
    return 0;
}