Cod sursa(job #71495)

Utilizator DastasIonescu Vlad Dastas Data 10 iulie 2007 19:47:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#define maxn 500001

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

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

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 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 = 1; i <= n; ++i )
    {
        while ( first <= last && i - Q[first].poz >= k )
            ++first;
        while ( last >= first && Q[last].v >= a[i] )
            --last;

//        printf("%d \n", Q[first].v );

        ++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 i = first; i <= last; ++i )
//            printf("%d ", Q[i].v);
//        printf("\n");
    }

//    printf("%d %d\n\n", first, last);

    int st = pmin - k + 1;
    int dr = pmin + k - 1;

    for ( int i = pmin; i >= st && i; --i )
        if ( a[i] < max )
        {
            st = 0;
            break;
        }
    for ( int i = pmin; i <= dr && i <= n; ++i )
        if ( a[i] < max )
        {
            dr = 0;
            break;
        }

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

//    int min = 100000000;
//    int start = 0, stop = 0;
//    for ( int i = 1; i <= last; ++i )
//        if ( Q[i].v < min )
//            min = Q[i].v, start = Q[i].poz, stop = Q[i].poz + k - 1;
//
//    for ( int i = 1; i <= n; ++i )
//        printf("%d %d\n", Q[i].v, Q[i].poz);
//
//    printf("\n");
//
//    fprintf(stdout, "%d %d %d\n", start, stop, min);

	return 0;
}