Pagini recente » Cod sursa (job #2883729) | Cod sursa (job #1061145) | soldiers | Cod sursa (job #310538) | Cod sursa (job #809765)
Cod sursa(job #809765)
#include <cstdio>
#define maxN 500005
FILE *f = fopen ("secventa.in","r");
FILE *g = fopen ("secventa.out","w");
int n, k, a[maxN], deque[maxN], begin, end, rez = -(1 << 30);
char s[maxN * 7];
void read()
{
int cnt = 0, x = 0, semn = 1;
fscanf (f, "%d%d\n", &n, &k);
fgets (s, maxN * 7, f);
for (int i = 0; s[i] != '\0'; i++)
if (s[i] >= '0' && s[i] <= '9')
x = x * 10 + s[i] - '0';
else if (s[i] == '-')
semn = -1;
else {
a[++cnt] = semn * x;
x = 0;
semn = 1;
}
}
void solve()
{
int front = 1, back = 0;
for (int i = 1; i <= n; i++) {
while (front <= back && a[i] <= a[deque[back]])
back--;
deque[++back] = i;
if (deque[front] == i - k)
front++;
if (i >= k) {
if (a[deque[front]] > rez) {
rez = a[deque[front]];
begin = i - k + 1;
end = i;
}
}
}
}
int main()
{
read();
solve();
fprintf (g, "%d %d %d\n", begin, end, rez);
fclose(f);
fclose(g);
return 0;
}