Cod sursa(job #2040280)

Utilizator BourucLiviuBouruc Petru Liviu BourucLiviu Data 15 octombrie 2017 16:51:32
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>

using namespace std;

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

deque <pair <int, int> > q;

int main()
{
    int n, k, x, Max = -9999999, st, dr;
    fin >> n >> k;
    for(int i = 1; i <= k; ++i)
    {
        fin >> x;
        while(!q.empty() && q.back().first >= x)
            q.pop_back();
        q.push_back(make_pair(x, i));
    }
    Max = q.front().first;
    st = 1; dr = k;
    for(int i = k + 1; i <= n; ++i)
    {
        fin >> x;
        while(!q.empty() && q.back().first >= x)
            q.pop_back();
        q.push_back(make_pair(x, i));

        if(i - q.front().second >= k) q.pop_front();

        if(q.front().first > Max)
        {
            Max = q.front().first;
            st = i-k+1;
            dr = i;
        }
    }
    fout << st << " " << dr << " " << Max;
    fin.close(); fout.close();
    return 0;
}