Cod sursa(job #1486475)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 14 septembrie 2015 21:59:01
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <queue>
#include <utility>

using namespace std;

int main()
{
    int N, K, i, a;
    pair<int, int> maximum = make_pair(-30001, -1);
    deque< pair<int, int> > dq;
    ifstream f("secventa.in");
    f >> N >> K;
    for (i = 1; i <= N; i++)
    {
        f >> a;
        if (!dq.empty())
        {
            if (i - dq.front().second == K)
                dq.pop_front();
            while (!dq.empty() && dq.back().first > a)
                dq.pop_back();
        }
        dq.push_back(make_pair(a, i));
        if (dq.size() == K && maximum.first < dq.front().first)
            maximum = dq.front();
    }

    ofstream g("secventa.out");
    g << maximum.second << " " << maximum.second + K - 1 << " " << maximum.first;
    g.close();
    return 0;
}