Cod sursa(job #1060835)

Utilizator mvcl3Marian Iacob mvcl3 Data 18 decembrie 2013 20:14:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <deque>

#define in "secventa.in"
#define out "secventa.out"
#define Max_Size 500009

std :: ifstream f(in);
std :: ofstream g(out);

int N, K;
int Beg, End, Base = -30009;
int A[Max_Size];
char line[10 * Max_Size];
std :: deque < int > DQ;

inline void Read_Data()
{
    f >> N >> K;

    f.getline(line, 10 * Max_Size);
    f.getline(line, 10 * Max_Size);

    int number = 0;
    short sign = 1;

    for(int i = 0; line[i]; ++i)
    {
        if(line[i] == '-') sign = -1;
        else
        if(line[i] != ' ' && line[i])
            number = number * 10 + line[i] - '0';
        else
        {
            A[ ++A[0] ] = number * sign;
            number = 0;
            sign = 1;
        }
    }

    A[ ++A[0] ] = number * sign;
}

inline void Solve()
{
    for(int i = 1; i <= N; ++i)
    {
        while(!DQ.empty() && A[DQ.back()] >= A[i])  DQ.pop_back();
        DQ.push_back(i);

        if(i - DQ.front() + 1 > K)  DQ.pop_front();

        if(A[ DQ.front() ] > Base && i >= K)
        {
            Base = A[ DQ.front() ];
            Beg = i - K + 1;
            End = i;
        }
    }
}

int main()
{
    Read_Data();
    Solve();

    g << Beg << ' ' << End << ' ' << Base << '\n';

    g.close();
    return 0;
}