Cod sursa(job #1108655)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 15 februarie 2014 21:58:56
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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;

    for (long i=1;i<=n;i++)
    {
        while (!(C[p]>='0' && C[p]<='9') && p<=length)
            p++;

        bool negative=false;
        if (C[p-1]=='-')
            negative=true;

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

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

        V[i]=x;

        int  auxV;

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

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

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

    return 0;
}