Cod sursa(job #430499)

Utilizator SpiderManSimoiu Robert SpiderMan Data 31 martie 2010 09:15:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>

#define MAX 5000015
#define hg 8192
#define oo 0x3f3f3f3f

int N, K;
int V[MAX], Q[MAX];
int st = 1, dr = 0, poz;
char ch[hg];

inline void cit (int &x)
{
    int semn = 0;
    x = 0;
    if (ch[0] == '\0') fread (ch, 1, hg, stdin);
    else while ((ch[poz] < '0' || ch[poz] > '9') && ch[poz]!='-')
            if (++poz == hg)
                fread (ch, 1, hg, stdin), poz = 0;

    if (ch[poz] == '-')
    {
        semn = 1;
        if (++poz == hg)
            fread(ch, 1, hg, stdin), poz = 0;
    }


    while (ch[poz] >= '0' && ch[poz] <= '9')
    {
        x = x * 10 + ch[poz] - '0';
        if (++poz == hg)
            fread (ch, 1, hg, stdin), poz = 0;
    }
    if (semn) x = -x;
}

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

    int i, max=-oo, rez;

    cit(N) , cit(K);


    for (i = 1; i <= N; i++)
        cit(V[i]);

    for (i = 1; i <= N; i++)
    {
        for (; st <= dr && V[i] <= V[Q[dr]]; --dr) ;

        Q[++dr] = i;

        for (; st <= dr && Q[st] <= i - K; st++) ;

        if (V[Q[st]] > max)
          max = V[Q[st]] , rez = i - K + 1;
    }

    printf("%d %d %d\n", rez, rez + K - 1, max);

    return 0;
}