Cod sursa(job #1185889)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 17 mai 2014 10:53:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>

using namespace std;

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

int k , v[500001] , stiva[500001] , st , dr;

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;

    in>>n>>k;

    for(i = 1 ; i <= n ; i++)
        in>>v[i];

    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;
}