Cod sursa(job #47853)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 4 aprilie 2007 09:20:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
// Problema secventa

#include <stdio.h>
#define MAX       500001
#define MAXIM     32000

int sir[MAX];
long poz[MAX];
int min[MAX];
long pr, ul, n, k, q;

int main()
{
    freopen( "secventa.in", "rt", stdin );
             scanf( "%ld %ld", &n, &k );
             long i;
             for( i=1; i<=n; i++ ) scanf( "%d", &sir[i] );
    fclose( stdin );
    
    poz[1] = 1;
    min[1] = sir[1];
    pr = ul = 1;
    int max = -MAXIM;
    for( i=2; i<=n; i++ )
         {
              while( ( ul > pr-1 ) && ( sir[i] < min[ul] ) ) ul--;
              ul++;
              min[ul] = sir[i];
              poz[ul] = i;
              while( ( pr < ul+1 ) && ( i - poz[pr]+1 > k ) ) pr++;
              if( ( i - poz[pr] <= k ) && ( min[pr] > max ) )
                  {
                      max = min[pr];
                      q = poz[pr];
                  }
         }
    
    freopen( "secventa.out", "wt", stdout );
             printf( "%ld %ld %d\n", q, q+k-1, max );
    fclose( stdout );
    return 0;
}