Cod sursa(job #1817118)

Utilizator Coroian_DavidCoroian David Coroian_David Data 27 noiembrie 2016 13:12:52
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

int n, k;

int st, dr;

int mx, start, en;

int d[500001];

int v[500001];

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;

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

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

    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &nr);

        v[i] = nr;

        if(i > k)
            stanga(i);

        dreapta(i);

        if(i >= k)
        {
            if(v[d[st]] > mx)
                mx = v[d[st]], start = i + 1 - 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;
}