Pagini recente » Cod sursa (job #1538830) | Cod sursa (job #1778596) | Cod sursa (job #1121694) | Cod sursa (job #2262261) | Cod sursa (job #1728357)
#include <fstream>
#include <cstdio>
#define NMAX 500005
using namespace std;
int n , k , st , dr , sol , p;
int v[NMAX] , dq[NMAX];
void read(int &x) {
int sign = 1;
char ch;
x = 0;
while (!isdigit(ch = getchar())) {
if (ch == '-') {
sign = -1;
}
else {
sign = 1;
}
}
do {
x = x * 10 + ch - '0';
}while (isdigit(ch = getchar()));
x *= sign;
}
int main() {
freopen("secventa.in" , "r" , stdin);
freopen("secventa.out" , "w" , stdout);
read(n) , read(k);
for (int i = 1; i <= n; ++i) {
read(v[i]);
}
st = dr = 1;
dq[1] = 1;
for (int i = 2; i <= k; ++i) {
int j = dr + 1;
while (j > 0 && v[i] <= v[dq[j]]) {
--j;
}
dr = j + 1;
dq[dr] = i;
}
sol = v[dq[st]];
p = 1;
for (int i = k + 1; i <= n; ++i) {
if (dq[st] < i - k + 1) {
++st;
}
int j = dr;
while (j >= st && v[i] <= v[dq[j]]) {
--j;
}
dr = j + 1;
dq[dr] = i;
if (v[dq[st]] > sol) {
sol = v[dq[st]];
p = i - k + 1;
}
}
printf("%d %d %d" , p , p + k - 1 , sol);
return 0;
}