Pagini recente » Borderou de evaluare (job #252922) | Borderou de evaluare (job #646910) | Cod sursa (job #2631276)
#include <fstream>
#include <deque>
using namespace std;
ifstream in ("secventa.in");
ofstream out ("secventa.out");
int a[500001];
deque <int> q;
char s[4000000];
int main(){
int n,k,semn=1,nr,cate=0;
in>>n>>k;
in.get();
in.getline(s, 3999999);
int i=0;
while (s[i]){
if (s[i]==' ')
i++;
else if (s[i]=='-'){
semn=-1;
i++;
}
else{
nr=0;
while (s[i] && s[i]>='0' && s[i]<='9'){
nr=nr*10+(s[i]-48);
i++;
}
a[++cate]=nr*semn;
semn=1;
}
}
for (i=1;i<=k;i++){
int x=a[i];
while (!q.empty() && a[q.back()]>=x)
q.pop_back();
q.push_back(i);
}
int maxx=a[q.front()];
int ind=k;
for (i=k+1;i<=n;i++){
int x=a[i];
while (!q.empty() && a[q.back()]>=x)
q.pop_back();
q.push_back(i);
if (q.front()<i-k+1)
q.pop_front();
if (a[q.front()]>maxx){
maxx=a[q.front()];
ind=i;
}
}
out<<ind-k+1<<' '<<ind<<' '<<maxx;
return 0;
}