Pagini recente » Cod sursa (job #3040410) | Cod sursa (job #1717806) | Cod sursa (job #2727385) | Cod sursa (job #270687) | Cod sursa (job #2161939)
#include <fstream>
#include <deque>
#include <climits>
#include <iostream>
#include <cstring>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
deque <int> d;
int n,k,i,maxim=INT_MIN,semn,nr,poz,v[50001];
char s[50001];
int main()
{
f>>n>>k;
char c=f.get();
f.getline(s,500100);
int j=0;
semn=1;
for(i=0;i<=strlen(s)-1;i++)
{
if(s[i]=='-')semn=-1;
else if('0'<=s[i]&&s[i]<='9')
{
nr=0;
while('0'<=s[i]&&s[i]<='9')
{nr=nr*10+(s[i]-'0');i++;}
j++;v[j]=nr*semn;
semn=1;
}
}
for(i=1; i<=k; i++)
{
while(d.size()>=1&&v[d.front()]>=v[i])
{
d.pop_front();
}
d.push_front(i);
}
if(v[d.back()]>maxim)
{
maxim=v[d.back()];
poz=k;
}
for(i=k+1; i<=n; i++)
{
while(d.size()>=1&&d.back()<=i-k)d.pop_back();
while(d.size()>=1&&v[d.front()]>=v[i])
{
d.pop_front();
}
d.push_front(i);
if(v[d.back()]>maxim)
{
maxim=v[d.back()];
poz=i;
}
}
g<<poz-k+1<<" "<<poz<<" "<<maxim;
return 0;
}