Cod sursa(job #1051818)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 10 decembrie 2013 16:55:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
# include <fstream>
# include <limits>
# define NMax 500001
using namespace std;

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

int n,k , Max ,st,dr;
short v[NMax];
int deck[NMax]; // deque

short Numar()
{
    char x;
    short t = 0 , y = 1;
    fin.get(x);
    while( x == ' ' || x == '\n' || x == '-' )
    {
        if( x == '-' )
            y *= -1;
        fin.get(x);
    }
    while( x >= '0' && x <= '9' )
    {
        t = t*10 + x-'0';
        fin.get(x);
    }
    return t*y;
}

void Citire()
{
    fin >> n >> k;
    for( int i = 1 ; i <= n ; ++i )
        fin >> v[i];
    fin.close();
}

void Rezolv()
{
    int ultim , prim , i;
    Max = numeric_limits<int>::min();
    ultim = 1;
    prim = 0;
    for( i = 1 ; i <= n ; ++i )
    {
        while( prim <= ultim && v[i] <= v[deck[ultim]] )
            --ultim;
        deck[++ultim] = i;
        if( deck[prim] == i-k )
            ++prim;
        if( deck[prim] > Max && i >= k )
        {
            Max = deck[prim];
            st = i-k+1;
            dr = i;
        }
    }
}

inline void Tipar()
{
    fout << st << ' ' << dr << ' ' << Max;
    fout.close();
}

int main()
{
    Citire();
    Rezolv();
    Tipar();
    return 0;
}