Cod sursa(job #48624)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 4 aprilie 2007 22:43:23
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
// Problema secventa

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

int nr[MAX][2];
long ul, pr;

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