Pagini recente » Cod sursa (job #2566801) | Cod sursa (job #621241) | Cod sursa (job #1367554) | Cod sursa (job #60904) | Cod sursa (job #47996)
Cod sursa(job #47996)
// 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] = n;
min[1] = sir[n];
pr = ul = 1;
int max = -MAXIM;
for( i=n-1; i>=n-k+2; i-- )
{
while( ( ul > pr -1 ) && ( sir[i] < min[ul] ) ) ul--;
ul++;
min[ul] = sir[i];
poz[ul] = i;
}
for(; i>=1; i-- )
{
while( ( ul > pr -1 ) && ( sir[i] < min[ul] ) ) ul--;
ul++;
min[ul] = sir[i];
poz[ul] = i;
while( ( pr < ul +1 ) && ( (poz[pr]-i) +1 > k ) ) pr++;
if( ( (poz[pr] -i) +1 <= 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;
}