Pagini recente » Cod sursa (job #1401522) | Cod sursa (job #193001) | Cod sursa (job #2265390) | Cod sursa (job #2269437) | Cod sursa (job #2146977)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
deque<int> dq;
int v[500005];
char s[3000005];
int main()
{ freopen("secventa.in", "r",stdin);
freopen("secventa.out", "w",stdout);
int n,k,i,maxx,st,dr,kk,semn,nn,nr;
scanf("%d%d\n", &n, &k);
gets(s);
nn=strlen(s);
kk=0;
i=0;
while(i<nn){
if(s[i]=='-'){
semn=s[i];
i++;
}
if(s[i]>='0' && s[i]<='9'){
nr=0;
while(i<nn && s[i]>='0' && s[i]<='9'){
nr=nr*10+s[i]-'0';
i++;
}
if(semn=='-')
nr*=-1;
semn='+';
v[++kk]=nr;
i++;
}
}
dq.push_back(1);
for(i=2; i<=k; i++){
while(!dq.empty() && v[dq.back()]>v[i])
dq.pop_back();
dq.push_back(i);
}
maxx=v[dq.front()];
st=1;
dr=k;
for(i=k+1; i<=n; i++){
while(!dq.empty() && v[dq.back()]>=v[i])
dq.pop_back();
while(!dq.empty() && dq.front()<=i-k)
dq.pop_front();
dq.push_back(i);
if(maxx<v[dq.front()]){
maxx=v[dq.front()];
st=i-k+1;
dr=i;
}
}
printf("%d %d %d", st, dr, maxx);
return 0;
}