Pagini recente » Cod sursa (job #275790) | Cod sursa (job #1602124) | Cod sursa (job #1451769) | Cod sursa (job #563280) | Cod sursa (job #1016840)
#include <cstdio>
#define dim 8192
#define N 500001
char ax[dim];
int pz;
inline void cit(int &x) {
x = 0;
while ((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
if (++pz == dim)
fread (ax, 1, dim, stdin), pz = 0;
int neg = 0;
if (ax[pz] == '-') {
neg = 1;
if (++pz == dim)
fread (ax, 1, dim, stdin), pz = 0;
}
while (ax[pz] >= '0' && ax[pz] <= '9') {
x = x * 10 + ax[pz] - '0';
if (++pz == dim)
fread (ax, 1, dim, stdin), pz = 0;
}
if (neg)
x = -x;
}
int a[N], H[N], poz[N];
int n, K;
int nh;
inline void swap(int i, int j) {
int t = H[i]; H[i] = H[j]; H[j] = t;
poz[H[i]] = i;
poz[H[j]] = j;
}
inline void upHeap(int i) {
while (i > 1 && a[ H[i] ] < a[ H[i >> 1] ])
swap(i, i >> 1), i >>= 1;
}
inline void downHeap(int i) {
int m = 0;
while (1) {
m = i;
if ((i << 1) <= nh && a[ H[i << 1] ] < a[ H[m] ])
m = i << 1;
if (((i << 1) | 1) <= nh && a[ H[(i << 1) | 1] ]< a[ H[m] ] )
m = (i << 1) | 1;
if (m != i)
swap(m, i), i = m;
else break;
}
}
int main() {
freopen ("secventa.in", "r", stdin);
freopen ("secventa.out", "w", stdout);
cit(n); cit(K);
int i, st = 0, dr = 0, res = -0x3f3f3f3f, u, v;
for (i = 1; i <= n; ++i)
cit(a[i]);
nh = K - 1;
for (i = 1; i <= nh; ++i)
H[i] = i, poz[i] = i;
for (i = nh / 2; i >= 1; --i)
downHeap(i);
for (i = K; i <= n; ++i) {
H[++nh] = i;
poz[i] = nh;
upHeap(nh);
if (a[ H[1] ] > res)
res = a[ H[1] ], st = i - K + 1, dr = i;
int u = poz[i - K + 1];
swap(nh--, u);
downHeap(u);
}
printf ("%d %d %d\n", st, dr, res);
}