Cod sursa(job #71531)

Utilizator DastasIonescu Vlad Dastas Data 10 iulie 2007 22:01:44
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <cstring>

#define maxn 500001

FILE *in = fopen("secventa.in","r"), *out = fopen("secventa.out","w");

int n;
int k;
int g;
int a[maxn] = {0};

char buf[10000];

void read()
{
    fscanf(in, "%d %d", &n, &k);

//    for ( int i = 1; i <= n; ++i )
//        fscanf(in, "%d", &a[i]);

    int l = 0;
    int minus = 0;
    while ( fgets(buf, 9999, in) )
    {
        l = strlen(buf);

        for ( int i = 0; i < l; ++i )
            if ( buf[i] >= '0' && buf[i] <= '9' )
                a[g] = (a[g]*10 + (buf[i] - '0'));
            else if ( buf[i] == '-' )
                a[g-1] *= -1, minus = 1;
            else if ( buf[i] = ' ' )
            {
                ++g;
                if ( minus == 1 )
                    a[g-1] *= -1;

                minus = 0;
            }
    }

    if ( minus )
        a[g] *= -1;

    for ( int i = 1; i <= g; ++i )
        printf("%d ", a[i]);

}

struct deque
{
    int poz, v;
};

deque Q[maxn];

int main()
{
    read();

    int first = 1, last = 0;
    Q[first].v = a[1];
    Q[first].poz = 1;

    int max = -300000000;
    //int min = 300000000;
    int pmin = 0;

    for ( int i = 2; i <= g; ++i )
    {
        while ( first < last + 1 && Q[first].poz < i - k + 1 )
            ++first;
        while ( last > first - 1 && Q[last].v > a[i] - 1 )
            --last;

        ++last;
        Q[last].v = a[i];
        Q[last].poz = i;

        if ( Q[first].v > max && Q[first].poz > k - 1 )
            max = Q[first].v, pmin = Q[first].poz;

//        for ( int j = first; j <= last; ++j )
//            printf("%d ", Q[j].v);
//        printf("\n");
    }

    int st = pmin;
    int dr = pmin;

    int p = max - 1;
    while ( a[st] > p )
        --st;
    ++st;
    while ( a[dr] > p && dr - st < k )
        ++dr;
    --dr;

    fprintf(out, "%d %d %d\n", st, dr, max);


    return 0;
}