Cod sursa(job #1108656)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 15 februarie 2014 22:04:41
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
/// Craciun Catalin
///  Secventa
///   www.infoarena.ro/problema/secventa
#include <iostream>
#include <fstream>
#include <cstring>
#include <deque>
#include <climits>

#define NMax 500005

using namespace std;

inline int maxim(int a, int b)
{
    if (a<b)
        return b;
    return a;
}

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

long n,k;
int V[NMax], q1, q2;
deque<int> A;
char C[7*NMax+5];
long length;

int main()
{
    f>>n>>k;
    f.getline(C,10);
    f.getline(C,NMax); length=strlen(C);

    f.close();

    long p=0;
    long minim=LONG_MIN;
    long poz=1;

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

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

            if (negative)
                x = (-1) * x;

            V[poz]=x;

            int  auxV;

            while (!A.empty() && V[poz]<V[A.back()])
                A.pop_back();
            A.push_back(poz);
            if (poz-k==A.front())
                A.pop_front();

            if (poz>=k)
            {
                auxV=V[A.front()];
                if (auxV>minim)
                {
                    minim=auxV;
                    q1=poz-k+1;
                    q2=poz;
                }
            }

            poz++;
        }
    }

    g<<q1<<' '<<q2<<' '<<minim<<'\n';
    g.close();

    return 0;
}