Cod sursa(job #96401)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 1 noiembrie 2007 14:36:37
Problema Secventa Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#include <string.h>
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define NMAX 500005

 int N, K, DEQ[NMAX], A[NMAX], first, last, i, max, p;

void update( int p ) // inserez valoare
 {
   while ( last >= first && A[DEQ[last]] >= A[p] ) last--;
   DEQ[++last] = p;
  }

int query( int p ) // calculez minimul 
 {
   while( first <= last && DEQ[first] < p ) first++;
   return A[DEQ[first]];
  }

      
int main()
 {
  FILE * fin, * fout;

  fin = fopen( FIN, "r" );
  fout = fopen( FOUT, "w" );
  fscanf( fin, "%d %d\n", &N, &K );
  for( i = 0; i < N; i++ ) fscanf( fin, "%d", A+i );
  first = 0; last = -1;
  for( i = 0; i < K; i++ ) update( i );
  max = query( 0 ); p = K - 1;
  for( i = K; i < N; i++ )
    {
      update( i );
      if ( max < query( i - K + 1 ) ) max = query( i - K + 1 ), p = i - K + 1;
     }
  fprintf( fout, "%d %d %d\n", p + 1, p + K, max  );
  fclose( fin );
  fclose( fout );
  return 0;
  }