Cod sursa(job #1003460)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 30 septembrie 2013 19:24:58
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <cstring>
#include <deque>
#include <cstdio>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n,k,bestbase;
int v[500001];
const int buff_size = (1<<16)-1;
char s[(1<<16)+1];

deque <int> d;

void parse ()
{
    freopen ("secventa.in","r",stdin);

    int sgn = 1,current=1,x=0;
    while (1)
    {
        fgets (s,1<<16,stdin);

        if (s[0]=='\0') break;

        for (int i=0; i<=buff_size; ++i)
        {
            if ('0' <= s[i] && s[i] <= '9')
            {
                x = x*10 + (s[i]-'0');
                continue;
            }

            if (s[i]==' '||s[i]=='\n')
            {
                x *= sgn;
                if (current == 1) n = x;
                else if (current == 2) k = x;
                else v[current-2] = x;
                ++current;
                x=0;
                sgn = 1;
                continue;
            }

            if (s[i]=='-')
            {
                sgn = -1;
                continue;
            }
        }
        s[0] = '\0';
    }
}

int main()
{
    freopen ("secventa.in","r",stdin);

    parse ();

    int i=1;

   for (; i<=k; ++i)
    {
        while (!d.empty() && v[i] < v[d.back()]) d.pop_back();
        d.push_back(i);
    }

    v[0] = -30001;

    for (i=k+1; i<=n; ++i)
    {
        while (!d.empty() && v[i] < v[d.back()]) d.pop_back();
        d.push_back (i);

        if (i - d.front() + 1 > k) d.pop_front ();

        if (v[d.front()] > v[bestbase]) bestbase = d.front();
    }

    for (int i=bestbase; i>=1; --i)
    {
        if (v[i] < v[bestbase])
        {
            fout<<i+1<<" "<<i+k<<" "<<v[bestbase];
            return 0;
        }
    }
    fout <<1<<" "<<k<<" "<<v[bestbase];

}