Cod sursa(job #71748)

Utilizator DastasIonescu Vlad Dastas Data 11 iulie 2007 15:30:47
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <cstring>

#define maxn 500001

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

int n;
int k;
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]);
}

//struct deque
//{
//    int poz, v;
//};
//
//deque Q[maxn];
int Qpoz[maxn];
int Qv[maxn];

int main()
{
    read();

    int first = 1, last = 1;

    int max = -300000000;
    int pmin = 0;
    int pmin2 = 0;

    int e = n + 1;

    int min = 300000000;
    for ( int i = 1; i < k + 1; ++i )
        if ( a[i] < min )
            min = a[i], pmin2 = i;

    if ( min > max )
        max = min, pmin = pmin2;

    for ( int i = 1; i < e; ++i )
    {

        while ( first < last + 1 && Qpoz[first] < i - k + 1 )
            ++first;
        while ( last > first - 1 && Qv[last] > a[i] - 1 )
            --last;

        ++last;
        Qv[last] = a[i];
        Qpoz[last] = i;

        if ( Qv[first] > max && Qpoz[first] > k - 1 )
            max = Qv[first], pmin = Qpoz[first];

//        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 && dr - st < k )
        --st;
    ++st;
    while ( a[dr] > p && dr - st < k )
        ++dr;
    --dr;

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


    return 0;
}