Cod sursa(job #1514180)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 30 octombrie 2015 19:53:37
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <queue>
#define NM 500005

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n, k, i, poz;
int v[NM], mx;
deque<int> d;

int main()
{
    fin >> n >> k;
    mx=-30005;
    for (i=1; i<=n; i++)
    {
        fin >> v[i];
        while (!d.empty() && v[i]<=d.back())
          d.pop_back();
        d.push_back(i);
        while (!d.empty() && d.front()<i-k+1)
          d.pop_front();
        if (!d.empty() && i>=k && v[d.front()]>mx)
        {
            poz=i;
            mx=v[d.front()];
        }
    }
    fout << poz-k+1 << " " << poz << " " << mx << '\n';
    fin.close();
    fout.close();
    return 0;
}