Cod sursa(job #1426335)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 29 aprilie 2015 14:47:11
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char C[1000000];
int v[500001], poz[500001];
short semn;
int i, n, k, j, fr, bk, lg;
int maxim = -999999, st, dr;

int main()
{
    f >> n >> k;
    n = 1;
    f.get();
    f.getline(C, sizeof(C));
    lg = strlen(C);
    for (i = 0; i < lg; i++)
    {
        if ('0' <= C[i] && C[i] <= '9')
            v[n] = v[n] * 10 + (C[i] - '0');
        else if (C[i] == '-')
            semn = -1;
        else
        {
            v[n] *= semn;
            semn = 1;
            n++;
        }
    }
    fr = 1, bk = 0;
    for (i = 1; i <= n; i++)
    {
        while (fr <= bk && v[i] <= v[poz[bk]])
            bk--;
        bk++, poz[bk] = i;
        if (poz[bk] - poz[fr] == k)
            fr++;
        if (i >= k && v[poz[fr]] > maxim)
            maxim = v[poz[fr]], st = poz[bk]-k+1, dr = poz[bk];
    }
    g << st << " " << dr << " " << maxim;
    return 0;
}