Cod sursa(job #1861601)

Utilizator netedu_andreiFII Andrei Netedu netedu_andrei Data 29 ianuarie 2017 07:21:36
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>

using namespace std;

struct elem
{
    int val;
    int poz;
};

deque<elem> q;

int main()
{
    ifstream  fin("secventa.in");
    ofstream fout("secventa.out");
    int n, k;
    fin >> n >> k;
    int capats = 1;
    int capatd = k;
    for(int i = 1; i <= k; i++)
    {
        elem x;
        fin >> x.val;
        x.poz = i;

        if(q.empty()) q.push_front(x);
        else
        {
            while(!q.empty() && q.front().val > x.val)
                q.pop_front();
            q.push_front(x);
        }
    }
    int minbaza = q.back().val;
    int bests = capats;
    int bestd = capatd;

    while(capatd < n)
    {
        capats++;
        capatd++;

        if(q.back().poz < capats) q.pop_back();

        elem x;
        fin >> x.val;
        x.poz = capatd;

        while(!q.empty() && q.front().val > x.val)
                q.pop_front();
            q.push_front(x);

        if(q.back().val > minbaza)
        {
            minbaza = q.back().val;
            bests = capats;
            bestd = capatd;
        }
    }
    fout << bests << ' ' << bestd << ' ' << minbaza << '\n';
    return 0;
}