Cod sursa(job #1108637)

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

#define NMax 500000
#define CMax 4000000

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[CMax];

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

    f.close();

    long p=0;
    long minim=LONG_MIN;

    for (long i=1;i<=n;i++)
    {
        while (!(C[p]>='0' && C[p]<='9'))
            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;

        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)
        {
            int auxV=V[A.front ()];
            if (auxV>minim)
            {
                minim=auxV;
                q1=i-k+1;
                q2=i;
            }
        }
    }

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

    return 0;
}