Cod sursa(job #2587071)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 21 martie 2020 23:11:45
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>
#include <string>

#define NMAX 500001

using namespace std;

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


deque < int > dq;
int n, k;
int v[NMAX];
string s;

int toNumber(int &index)
{
    while (s[index] == ' ')
        ++index;

    char sign = '+';

    if (s[index] == '-') {
        sign = '-';
        ++index;
    }

    int nr = 0;

    while (s[index] >= '0' && s[index] <= '9') {

        nr = nr*10 + (s[index] -'0');

        ++index;
    }

    if (sign == '+')
        return nr;
    return -nr;
}

int main()
{
    fin >> n >> k;
    fin.get();
    getline(fin, s);

    int index = 0;
    int maximum = -30005, left, right;

    for (int i = 1; i <= n; i++)
    {
        v[i] = toNumber(index);

        while (!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();

        dq.push_back(i);

        if (i - dq.front() + 1 > k)
            dq.pop_front();

        if (maximum < v[dq.front()] && i >= k)
        {
            maximum = v[dq.front()];
            right = i;
            left = i - k + 1;
        }
    }

    fout << left << ' ' << right << ' ' << maximum;
}