Cod sursa(job #71854)

Utilizator DastasIonescu Vlad Dastas Data 11 iulie 2007 23:48:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <cstdio>
#include <cstring>

#define maxn 500001
#define inf 3000000

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

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

char buf[1024];

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

    e = n + 1;
    int t = 1;
    int minus = 0;
    while ( fgets(buf, 1024, in) )
    {
        int l = strlen(buf);

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

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

//struct deque
//{
//    int poz, v;
//};

//deque Q[maxn];

int main()
{
    read();
//
//    int first = 1, last = 1;
//
//    int max = -inf;
//
//    int pmin = 0;
//
//    int min = inf;
//    for ( int i = 1; i < k + 1; ++i )
//        if ( a[i] < min )
//            min = a[i], pmin = i;
//
//    max = min;
////    min = inf;
//
//    int st = 0;
//    int dr = 0;
//
//    for ( int i = 1; i < e; ++i )
//    {
//        while ( first < last + 1 && Q[first].poz <= i - k )
//            ++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 )
//            max = Q[first].v, pmin = Q[first].poz;
//
////        for ( int j = first; j <= last; ++j )
////            printf("%d ", Q[j].v);
////        printf("\n");
//    }
//
//    dr = st = pmin;
//
//    int p = max - 1;
//
//    while ( a[st] > p && st )
//        --st;
//    ++st;
//
//    while ( a[dr] > p && dr - st < k )
//        ++dr;
//    --dr;

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

    int st = 0, dr = 0, min = inf, max = -inf;
    for ( int i = 1; i <= e; ++i )
    {
        min = inf;
        int poz = i;

        if ( i + k > e )
            break;

        int l = i + k;
        int t = i;
        for ( int j = i; j < l && j < e; ++j )
            if ( a[j] < min )
                min = a[j], poz = j, i = poz;

        if ( min > max && l <= e )
            max = min, st = t, dr = t + k - 1;
    }

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

    return 0;
}