Pagini recente » Cod sursa (job #1654569) | Cod sursa (job #1152192) | Votati personajul preferat Infoarena | Cod sursa (job #857880) | Cod sursa (job #2776203)
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("secventa.in");
ofstream cout("secventa.out");
int a[500005];
deque<int>dq;
int main()
{
int n,k,poz1,poz2,poz3,max1=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=k;i++)
{
while(dq.size()>0 and a[i]<=a[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
}
max1=a[dq.front()];
poz1=dq.front();
for(int i=k+1;i<=n;i++)
{
while(dq.size()>0 and a[i]<=a[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
while(dq.size()>0 and dq.front()<i-k+1)
{
dq.pop_front();
}
if(a[dq.front()]>max1)
{
max1=a[dq.front()];
poz1=dq.front();
poz2=i;
}
}
cout<<poz2-k+1<<" "<<poz2<<" "<<max1;
/*
int n,k,max1=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=k+1;i++)
{
while(dq.size()>0 and a[i]<=a[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
while(dq2.size()>0 and a[i]>=a[dq2.back()])
{
dq2.pop_back();
}
dq2.push_back(i);
}
max1=a[dq2.front()]-a[dq.front()];
//cout<<a[dq2.front()]<<" "<<a[dq.front()]<<" "<<max1<<endl;
for(int i=k+2;i<=n;i++)
{
//cout<<i<<endl;
while(dq.size()>0 and a[i]<=a[dq.back()])
{
dq.pop_back();
}
dq.push_back(i);
while(dq.size()>0 and dq.front()<i-k)
{
dq.pop_back();
}
while(dq2.size()>0 and a[i]>=a[dq2.back()])
{
dq2.pop_front();
}
dq2.push_back(i);
while(dq.size()>0 and dq2.front()<i-k)
{
dq2.pop_front();
}
max1=max(max1,(a[dq2.front()]-a[dq.front()]));
}
cout<<max1;
*/
return 0;
}