Pagini recente » Cod sursa (job #2943392) | Cod sursa (job #2938371) | Cod sursa (job #2394548) | Cod sursa (job #2040866) | Cod sursa (job #16449)
Cod sursa(job #16449)
#include <cstdio>
using namespace std;
int N, K;
int i, j;
int RMQ[19][500001];
int v[500001];
int MINU(int a, int b) {
int lg = b - a + 1;
int i, j;
for (i=19; i>=0; i--) if ((1<<i) <=lg ) break;
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=1; i< N+1; i++) {
int X;
scanf("%d", &X);
v[i] = X;
RMQ[0][i] = X;
}
int X = 1, X2 = 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;
}