Cod sursa(job #1817135)

Utilizator Coroian_DavidCoroian David Coroian_David Data 27 noiembrie 2016 13:31:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>

#include <climits>

using namespace std;

FILE *f, *g;

int n, k;

int st, dr = -1;

int mx = INT_MIN, start, en;

int d[500001];

int v[500001];

char s[3000103];

void stanga(int i)
{
    if (i - k == d[st])
        st++;
}

void dreapta(int i)
{
    while (st <= dr && v[i] <= v[d[dr]])
        dr --;

    d[++ dr] = i;
}

void solve()
{
    int i, nr;
    int sign, curChar = 0;

    f = fopen("secventa.in", "r");

    fscanf(f, "%d%d\n", &n, &k);

    fgets(s, 3000101, f);

    for(i = 1; i <= n; i ++)
    {
        nr = 0;
        sign = 1;

        if(s[curChar] == '-')
            sign = -1, curChar ++;

        while(s[curChar] >= '0' && s[curChar] <= '9')
        {
            nr = nr * 10 + (s[curChar] - '0');

            curChar ++;
        }

        curChar ++;

        nr *= sign;

        v[i] = nr;

        if(i > k)
            stanga(i);

        dreapta(i);

        if(i >= k)
        {
            if(v[d[st]] > mx)
                mx = v[d[st]], start = i - k + 1, en = start + k - 1;
        }
    }
}

void printFile()
{
    g = fopen("secventa.out", "w");

    fprintf(g, "%d %d %d\n", start, en, mx);

    fclose(g);
}

int main()
{
    solve();

    printFile();

    return 0;
}