Mai intai trebuie sa te autentifici.

Cod sursa(job #2674587)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 19 noiembrie 2020 17:49:00
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int NMAX = 500000;
const int BUFFER_SIZE = 100000;

deque<int> dq;

int n;
int v[1 + NMAX];

char sir[BUFFER_SIZE];
int pos = BUFFER_SIZE;

void read()
{
    bool added = false;

    int nrCrt = 0;
    int i = 1;

    while (i <= n)
    {
        if (pos == BUFFER_SIZE)
        {
            pos = 0;
            in.get(sir, BUFFER_SIZE);
        }

        if ('0' <= sir[pos] && sir[pos] <= '9')
        {
            nrCrt = nrCrt * 10 + (int)(sir[pos] - '0');
            pos++;
            added = true;
        }
        else if (sir[pos] == '-')
        {
            v[i] = -1;
            pos++;
        }
        else
        {
            if (added)
            {
                if (v[i] == -1)
                {
                    v[i] = -nrCrt;
                }
                else
                {
                    v[i] = nrCrt;
                }
                i++;
                nrCrt = 0;
                added = false;
            }
            pos++;
        }
    }
}

int main()
{
    int k;

    in >> n >> k;

    in.get();

    int solMax = -30001;
    int solSt = -1;
    int solDr = -1;

    read();

    for (int i = 1; i <= k - 1; i++)
    {
        while (!dq.empty() && v[dq.front()] >= v[i])
        {
            dq.pop_front();
        }

        dq.push_front(i);
    }

    for (int i = k; i <= n; i++)
    {
        while (!dq.empty() && v[dq.front()] >= v[i])
        {
            dq.pop_front();
        }

        dq.push_front(i);

        if (dq.back() < i - k + 1)
        {
            dq.pop_back();
        }

        if (v[dq.back()] > solMax)
        {
            solMax = v[dq.back()];

            solSt = i - k + 1;
            solDr = i;
        }
    }

    out << solSt << ' ' << solDr << ' ' << solMax << '\n';

    return 0;
}