Pagini recente » Cod sursa (job #3221904) | Cod sursa (job #2888118) | Cod sursa (job #2411697) | Borderou de evaluare (job #486561) | Cod sursa (job #1016832)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 500001
#define T (u >> 1)
#define L (u << 1)
#define R (L | 1)
int i, n, N, K, dr;
int left, st;
int MX;
int poz[NMAX];
int v[NMAX];
int H[NMAX];
void upheap(int u) {
while (u != 1 && v[H[u]] < v[H[T]]) swap(H[u], H[T]), poz[H[u]] = u, poz[H[T]] = T, u = T;
}
void downheap(int u) {
while (1) {
int m = u;
if (L <= n && v[H[L]] < v[H[m]]) m = L;
if (R <= n && v[H[R]] < v[H[m]]) m = R;
if (m == u)
break;
swap(H[u], H[m]);
poz[H[u]] = u;
poz[H[m]] = m;
u = m;
}
}
int main() {
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%i%i", &N, &K);
left = 1;
MX = -30001;
for (i = 1; i <= N; ++i) {
scanf("%i", &v[i]);
H[++n] = i;
poz[i] = n;
upheap(n);
if (i >= K){
if (v[H[1]] > MX)
st = i - K + 1, dr = i, MX = v[H[1]];
int u = poz[i - K + 1];
swap(H[u], H[n]);
poz[H[u]] = u;
poz[H[n]] = n;
--n;
downheap(u);
}
}
printf("%i %i %i", st, dr, MX);
return 0;
}