Cod sursa(job #1185916)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 17 mai 2014 11:17:04
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

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

int k , v[500001] , stiva[500001] , st , dr;
char linie[3500000];

inline void stanga(int i)
{
    if(i - k == stiva[st])
        st++;
}

inline void dreapta(int i)
{
    while(st <= dr && v[i] <= v[stiva[dr]])
        dr--;

    stiva[++dr] = i;
}

int main()
{
    int n , i, baza , a, val, semn = 1;

    in>>n>>k>>ws;
    /*
    for(i = 1 ; i <= n ; i++)
        in>>v[i];
    */
    in.getline(linie, 3500000);
    n = 0;
    val = 0;
    for(i = 0; linie[i] != '\0' && linie[i] != '\n'; i++)
    {
        if(linie[i] == ' ')
        {
            v[++n] = semn * val;
            val = 0;
            semn = 1;
        }
        if(linie[i] == '-')
            semn  = -1;
        if(linie[i] >= '0' && linie[i] <= '9')
            val = val * 10 + linie[i] - '0';
    }
    v[++n] = semn * val;
    st = 1;
    dr = 0;
    baza = -30001;

    for(i = 1 ; i <= n ; i++)
    {
        dreapta(i);
        stanga(i);

        if(i >= k && baza < v[stiva[st]])
        {
            baza = v[stiva[st]];
            a = i;
        }
    }

    out<<a - k + 1<<' '<<a<<' '<<baza<<'\n';

    return 0;
}