Pagini recente » Cod sursa (job #3285104) | Cod sursa (job #2266070) | Cod sursa (job #1147265) | Cod sursa (job #603883) | Cod sursa (job #742124)
Cod sursa(job #742124)
#include <cstdio>
#include <cstdlib>
using namespace std;
#define nmax 500010
int v[nmax], deque[nmax], n, k, max = -nmax, start, end, front, back;
char s[8*nmax];
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int i, j = 0;
bool ok = false;
scanf("%i %i\n", &n, &k);
fgets(s,8*nmax,stdin);
int number = 0;
for(i = 1; i <= n; ++i)
{
ok = false;
while(s[j] == ' ') j++;
if(s[j] == '-')
{
j++;
ok = true;
}
number = 0;
while(s[j] >='0' && s[j] <='9')
{
number = number * 10 + (s[j] - '0');
j++;
}
if(ok) v[i] = number * (-1);
else v[i] = number;
}
front = 1;
back = 1;
deque[1] = 1;
for(i = 2; i < k; ++i)
{
while(front <= back && v[i] <= v[ deque[back] ]) back--;
deque[++back] = i;
}
for(i = k; i<=n; ++i)
{
while(front <= back && v[i] <= v[ deque[back] ]) back--;
deque[++back] = i;
if(v[ deque[front] ] > max)
{
max = v[ deque[front] ];
start = i - k + 1;
end = i;
}
if(deque[front] < i - k + 2) front++;
}
printf("%i %i %i", start, end, max);
return 0;
}