Cod sursa(job #1108781)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 16 februarie 2014 12:56:10
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
/// Catalin Craciun
///  Secventa
///   www.infoarena.ro/problema/secventa
#include <fstream>
#include <iostream>
#include <cstring>

#define NMax 500005
#define DMax 4000000

using namespace std;

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

char C[DMax];
int V[NMax];
long n,k,x,y,maxim=-1<<30;
int Deque[NMax],Front,Back;

int main()
{
    f>>n>>k;

    f.getline(C, 10);
    f.getline(C, DMax);

    f.close();

    long i=1;
    long length=strlen(C);

    for (long q=0;q<length;q++)
        if (C[q]>='0' && C[q]<='9')
        {
            bool negativ=false;
            if (C[q-1]=='-')
                negativ=true;

            int x=0;
            while (C[q]>='0' && C[q]<='9')
            {
                x=x*10+(C[q]-'0');
                q++;
            }

            if (negativ)
                x=-x;

            V[i++]=x;
        }

    for (i=1;i<=n;i++)
    {
        while (Front<=Back && V[i]<=V[Deque[Back]]) Back--;
        Deque[++Back]=i;
        if (Deque[Front]==i-k) Front++;
        if (i>=k)
        {
            if (V[Deque[Front]]>maxim)
            {
                maxim=V[Deque[Front]];
                x=i-k+1; y=i;
            }
        }
    }

    g<<x<<' '<<y<<' '<<maxim<<'\n';
    g.close();

    return 0;
}