Pagini recente » Cod sursa (job #720195) | Cod sursa (job #258533) | Cod sursa (job #2100574) | Cod sursa (job #1112030) | Cod sursa (job #16451)
Cod sursa(job #16451)
#include <cstdio>
using namespace std;
int N, K;
int i, j;
int RMQ[19][500001];
int v[500001];
int level;
int MINU(int a, int b) {
int lg = b - a + 1;
int i, j;
i = level;
int X = (1<<i);
int ret = RMQ[i][a];
if (RMQ[i][b-X+1] < ret) ret = RMQ[i][b-X+1];
return ret;
}
int main() {
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
scanf("%d %d", &N, &K);
for (i=19; i>=0; i--) if ((1<<i) <=K) break;
level = i;
for (i=1; i< N+1; i++) {
int X;
scanf("%d", &X);
v[i] = X;
RMQ[0][i] = X;
}
int X = 1, X2 = 1;
X = 1;
for (i=1; ;i++) {
X<<=1;
if (X > N) break;
for (j=1; j+X-1 <=N; j++) {
RMQ[i][j] = RMQ[i-1][j];
if (RMQ[i-1][j+X-X2] < RMQ[i][j]) RMQ[i][j] = RMQ[i-1][j+X-X2];
}
X2 = X;
}
int sol = -31111, st, dr;
for (i=1; i<=N-K+1; i++) {
//minu pe i, i + K -1
int A = i, B = i+K-1;
int m = MINU(A, B);
if (m > sol) {sol = m; st = i, dr = i+K-1;}
}
printf("%d %d %d\n", st, dr, sol);
return 0;
}