Cod sursa(job #531277)

Utilizator skullLepadat Mihai-Alexandru skull Data 9 februarie 2011 12:31:22
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
using namespace std;
#define nmax 500005
#define mx 4194304

int vec[nmax], dq[nmax];
int N, K;
char sir[mx];

int main ()
{
    freopen("secventa.in","r",stdin);
    scanf("%d%d", &N, &K);
    int i = 0, ind, x, sw;
    fgets(sir,mx,stdin);
    fgets(sir,mx,stdin);
    ind = 0;
    back:
    x = 0;
    sw = 1;
    for( ;!(sir[ind]>='0' && sir[ind]<='9');ind++); /// determin daca are '-' in fata
    if(sir[ind-1]=='-')
        sw=-1;
    for(;sir[ind]>='0' && sir[ind]<='9';ind++)
        x=x*10+(sir[ind]-'0');
    vec[++i]=sw*x;
    if(i != N)
    goto back;

    for (i = 1; i <= N; ++i) scanf("%d", &vec[i]);
    int st = 1, dr = 1, maxim = -30005, a, b;
    dq[1] = vec[1];
    for (i = 2; i <= N; ++i)
    {
        while (st <= dr && dq[dr]>vec[i]) dr--;
        dq[++dr] = vec[i];
        if (i > K && dq[st] == vec[i-K]) st++;
        if (i >= K)
            if ( dq[st] > maxim )
            {
                maxim = dq[st];
                a = i-K+1;
                b = i;
            }
    }
    freopen("secventa.out","w",stdout);
    printf("%d %d %d\n", a, b, maxim);
    return 0;
}