Pagini recente » Cod sursa (job #1375516) | Cod sursa (job #3200405) | Cod sursa (job #1944504) | Cod sursa (job #951726) | Cod sursa (job #266284)
Cod sursa(job #266284)
#include <stdio.h>
#include <string.h>
#define nmax 500001
#define min(a,b) ((a>b)?b:a)
int a[nmax],n,k;
char text[1<<22];
int i,j,l,min,deque[nmax],pos[nmax],first,last,max,maxi,maxj;
int main(){
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d %d",&n,&k);
gets(text);gets(text);
j = strlen(text);
for(l=1;i<j;++i){
if(text[i] == '-') min = 1;
else if(text[i] == ' '){
if(min)
a[l] *= -1;
++l;
min=0;}
else a[l] = a[l] * 10 + text[i] - '0';}
if(min) a[l] *= -1;
first = last = 1;
deque[1] = a[1];
pos[1] = 1;
max = -(1<<30);
for(i=2; i<k; ++i)
{
while(a[i] <= deque[last] && last > 0) --last;
deque[++last] = a[i];
pos[last] = i;
}
for(i=k; i<=n; ++i)
{
while (i - pos[first] >= k) ++first;
min = min(a[i], deque[first]);
if(min > max){
max = min;
maxi = i-k+1;
maxj = i;
}
while (a[i] <= deque[last] && last > 0) --last;
deque[++last] = a[i];
pos[last] = i;
if(first>last)
first = last;
}
printf("%d %d %d",maxi,maxj,max);
return 0;
}