Cod sursa(job #1101502)

Utilizator negreadumitruNegrea Dumitru negreadumitru Data 8 februarie 2014 16:21:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
using namespace std;
#define max 500001
int elem[max], deque[max], first = 1, last = 0, N, k,nr,signTrue,p;
char caractere[7*max];
int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    int inceput_max, sfarsit_max, i,maxim=-30001;
    f >> N >> k;
    f.getline(caractere, 2);
    f.getline(caractere, 3500007);
    i = 0;
    while (caractere[i] != '\0')
    {
        if (caractere[i] >= '0' && caractere[i] <= '9')
            nr = nr * 10 + (caractere[i] - '0');
        else if (caractere[i] == '-') signTrue = 1;
             else if (caractere[i] == ' ')
             {
                 elem[++p] = nr;
                 if (signTrue) elem[p] = -elem[p];
                 signTrue = nr = 0;
             }
        ++i;
    }

    elem[++p] = nr;
    if (signTrue) elem[p] = -elem[p];
    for (i = 1; i <= N; ++i)
    {
        while(first <= last && elem[i] < elem[deque[last]]) --last;
        deque[++last] = i;
        if (deque[first] + k == i) ++first;
        if (i >= k && elem[deque[first]]>maxim)
        {
            maxim = elem[deque[first]];
            inceput_max = i - k + 1;
            sfarsit_max = i;
        }
    }
    g << inceput_max << " " << sfarsit_max << " " << maxim;
    f.close();
    g.close();
}