Pagini recente » Cod sursa (job #781540) | Cod sursa (job #1240145) | Cod sursa (job #389738) | Cod sursa (job #2857064) | Cod sursa (job #33728)
Cod sursa(job #33728)
#include <cstdio>
#include <cmath>
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define MAX 500500
#define LOG 20
inline long min(long x, long y) {
return (x<y) ? x:y;
}
long V[LOG][MAX];
long A[MAX], N, K;
long i,shl;
long dr, st, bz;
long poz, act;
inline long f(long x, long y) { // baza secventei de la x la y
long d = (long) (log(y-x)/log(2));
return min(V[d][x],V[d][y-(1<<d)+1]);
}
int main() {
freopen(FIN, "r", stdin);
scanf("%ld %ld", &N, &K);
for (i=1; i<=N; ++i)
scanf("%ld", A+i);
fclose(stdin);
for (i=1; i<=N; ++i)
V[0][i] = A[i];
for (shl=1; (1<<shl) <= N; ++shl)
for (i=1; i<=N; ++i)
if ( i+(1<<(shl-1))<=N )
V[shl][i] = min(V[shl-1][i], V[shl-1][(1<<(shl-1))+i]);
else
V[shl][i] = V[shl-1][i];
st = 1; dr=K;
bz = f(st,dr);
poz = 1; act = bz;
for (i=K+1; i<=N; ++i) {
act = min(act, A[i]);
if ( act<f(i-K+1,i) ) {
poz = i-K+1;
act = f(i-K+1,i);
}
if ( act>bz ) {
bz = act;
st = poz; dr = i;
}
}
freopen(FOUT, "w", stdout);
printf("%ld %ld %ld\n", st,dr,bz);
fclose(stdout);
return 0;
}