Pagini recente » Monitorul de evaluare | Cod sursa (job #1683906) | Istoria paginii utilizator/cristina.moraru | Cod sursa (job #1707028) | Cod sursa (job #471853)
Cod sursa(job #471853)
# include <stdlib.h>
# include <cstdio>
using namespace std;
int n, k, front, back, a[500005], deque[500005], max, pozmax, bestpoz;
int main()
{int i;
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d",&n,&k);
for (i = 1; i <= n; i++)
scanf("%d",&a[i]);
front = 1; back = 0; max = -1000; pozmax = -1000;
for (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]] > max && front <= n - k + 1)
{
pozmax = deque[front];
max = a[deque[front]];
}
}
if (pozmax == 1) bestpoz = 1;
if (pozmax == 2) bestpoz = 1;
if (pozmax == n - 1) bestpoz = n - 2;
if (pozmax == n) bestpoz = n - 2;
if (pozmax > 2 && pozmax < n -1)
{
if (a[pozmax - 2] > a[pozmax] && a[pozmax - 1] > a[pozmax] ) bestpoz = pozmax - 2;
else if (a[pozmax - 1] > a[pozmax] && a[pozmax + 1] > a[pozmax]) bestpoz = pozmax - 1;
else if (a[pozmax + 1] > a[pozmax] && a[pozmax + 2] > a[pozmax]) bestpoz = pozmax;
}
}
printf("%d %d %d", bestpoz, bestpoz + k - 1, max);
return 0;
}