Cod sursa(job #71436)

Utilizator DastasIonescu Vlad Dastas Data 10 iulie 2007 15:26:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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];

/*
8 3
-1 2 3 1 0 4 8 6

Q:          poz         v
            1           -1
            2           2

*/

int main()
{
    read();

    int first = 1, last = 1;

    for ( int i = 1; i <= n; ++i )
    {
        Q[last].v = a[i];
        Q[last++].poz = i;

		while ( first <= last && Q[first].poz <= i - k + 1 )
            ++first;
		while ( last >= first && Q[last].v >= a[i] )
            --last;
    }

    //printf("%d %d\n\n\n", first, last);
    int min = 100000000;
    int start, stop;
    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;

    //printf("\n\n");

    //for ( int i = 1; i <= n; ++i )
       // printf("%d %d\n", Q[i].v, Q[i].poz);

    fprintf(out, "%d %d %d\n", start, stop, min);

	return 0;
}