Pagini recente » Cod sursa (job #1775975) | Cod sursa (job #2190583) | Cod sursa (job #408324) | Cod sursa (job #1738838) | Cod sursa (job #1372473)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define inFile "secventa.in"
#define outFile "secventa.out"
#define MAX_N 500001
#define INF 1<<30
int a[MAX_N], left[MAX_N], right[MAX_N], s[MAX_N];
char str[MAX_N * 6];
int main() {
freopen(inFile, "r", stdin);
freopen(outFile, "w", stdout);
int n, k, val, l, sgn, j;
register int i, lev;
scanf("%d %d\n", &n, &k);
gets(str);
l = strlen(str);
for(i = 0, j = 1; i < l; ) {
if(str[i] == ' ') {
i++;
continue;
}
if(str[i] == '-') sgn = -1, ++i;
else sgn = 1;
for(; '0' <= str[i] && str[i] <= '9'; i++)
a[j] = a[j] * 10 + str[i] - '0';
a[j] *= sgn;
j++;
}
for(i = 1, lev = 1; i <= n; i++) {
while(lev > 1 && a[i] < a[s[lev-1]])
right[s[lev-1]] = i, lev--;
s[lev++] = i;
}
while(lev > 1)
right[s[lev-1]] = n+1, lev--;
for(i = n, lev = 1; i; i--) {
while(lev > 1 && a[i] < a[s[lev-1]])
left[s[lev-1]] = i, lev--;
s[lev++] = i;
}
while(lev > 1)
left[s[lev-1]] = 0, lev--;
int base_max = -INF, i_max = -1, j_max = -1;
for(i = 1; i <= n; i++) {
if(right[i] - left[i] - 1 >= k) {
if(a[i] > base_max) {
base_max = a[i];
i_max = left[i]+1;
j_max = max(i, left[i]+k);
}
}
}
printf("%d %d %d\n", i_max, j_max, base_max);
return 0;
}