Pagini recente » Cod sursa (job #1152005) | Cod sursa (job #1307202) | Cod sursa (job #1931585) | Cod sursa (job #1128026) | Cod sursa (job #79294)
Cod sursa(job #79294)
#include <stdio.h>
#define MIN( a, b ) ( (a) < (b) ) ? a : b
#define MAX( a, b ) ( (a) > (b) ) ? a : b
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define NMAX 500050
int main()
{
FILE * fin;
FILE * fout;
int A[NMAX], DEQ[NMAX];
int N, K, i, j, first, last, left, right, min;
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++ )
{
while ((last >= first ) && ( A[DEQ[last]] > A[i] ) ) last--; // insert in deque
last++;
DEQ[last] = i;
}
min = A[DEQ[first]]; right = K - 1;
for( i = K; i < N; i++ )
{
while ( (last >= first ) && ( A[DEQ[last]] > A[i] )) last--; // insert in deque
last++;
DEQ[last] = i;
while (( first <= last ) && ( i - DEQ[first] >= K )) first++; // stabilize deque
if ( A[DEQ[first]] > min )
{
min = A[DEQ[first]];
right = i;
}
}
fprintf( fout, "%d %d %d\n", right - K + 2, right + 1, min );
fclose( fin );
fclose( fout );
return 0;
}