Cod sursa(job #1510042)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 15:10:06
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <deque>
using namespace std;

int a[500001];
deque<int> D;
string s;
int pos = 0;

int nextInt()
{
    while (s[pos] == ' ' && pos < s.size()) ++pos;

    int Ret = 0;
    int sgn = 1;
    if (s[pos] == '-') sgn = -1, ++pos;
    while (s.size() > pos && s[pos] != ' ')
    {
        Ret *= 10;
        Ret += s[pos] - '0';
        ++pos;
    }

    return Ret * sgn;
}

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

    int N,K;

    fin >> N >> K;

    fin.get();
    getline(fin,s);

    for (int i = 1; i <= N; i++)
        a[i] = nextInt();

    int best = -30001,from = 0;

    for (int i = 1; i <= N; i++)
    {
        while (!D.empty() && i - D.front() + 1 > K)
            D.pop_front();
        while (!D.empty() && a[D.back()] > a[i])
            D.pop_back();

        D.push_back(i);

        if (i >= K && a[D.front()] > best)
        {
            best = a[D.front()];
            from = i;
        }
    }

    fout << from - K + 1 << " " << from << " " << best;
}