Cod sursa(job #1139650)

Utilizator sorynsooSorin Soo sorynsoo Data 11 martie 2014 13:03:26
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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 D[NMax], st, dr;

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

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

    f.close();

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

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

    /// Parcurgere
    for (i=1;i<=n;i++)
    {
        g<<"\n";
        while (st<=dr && V[i]<=V[D[dr]])
            dr--;
        D[++dr]=i;
        for(int j=st; j<=dr; j++)
            g<<V[D[j]]<<" ";
        g<<"\n";

         if (D[st]==i-k)
            st++;

        if (i>=k)
        {
            if (V[D[st]]>maxim)
            {
                maxim=V[D[st]];
                x=i-k+1; y=i;
            }
        }
    }

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

    return 0;
}