Cod sursa(job #2268151)

Utilizator victorv88Veltan Victor victorv88 Data 24 octombrie 2018 15:32:32
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
using namespace std;

deque<int>deck;

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

int n, lmin, val[500005], indexinceput,indexfinal,maxi=-9999999,lungime, nr,ind=1;
char sir[6000000];

void citire()
{
    f.getline(sir,6000000);
    lungime=strlen(sir);
    for (int i=0; i<lungime; i++)
    {
        nr=0;
        if (sir[i]=='-')
        {
            i++;
            while (sir[i]>='0'&& sir[i]<='9')
                nr=nr*10-(sir[i]-'0'),i++;
            val[ind++]=nr;
        }
        else
        {
            while (sir[i]>='0'&& sir[i]<='9')
                nr=nr*10+(sir[i]-'0'),i++;
                val[ind++]=nr;
        }
    }
}

int main() {
    f >>n >> lmin;
    f.get();
    citire();
    for (int i=1; i< lmin; i++)
    {

        while (!deck.empty() && val[deck.back()]>val[i])
            deck.pop_back();
        deck.push_back(i);
    }

    for (int i=lmin; i<=n; i++)

    {

        f >> val[i];

        while (!deck.empty() && val[deck.back()]>val[i])

            deck.pop_back();

        deck.push_back(i);

        if (i-deck.front()==lmin)

            deck.pop_front();

        if (!deck.empty() && i>=lmin && val[deck.front()]>maxi)

        {

            maxi=val[deck.front()];

            indexfinal=i;

            indexinceput=indexfinal-lmin+1;

        }



    }

    g << indexinceput <<' ' <<indexfinal <<' ' << maxi;

    return 0;

}