Pagini recente » Cod sursa (job #2588129) | Cod sursa (job #944248) | Cod sursa (job #376104) | Cod sursa (job #2331326) | Cod sursa (job #1639815)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
char s[2000006];
int l,ok,t,in,sf,nr,j,Max,Front,Back,n,k,i,a[500001],dq[500001];
int get()
{
int x=0;ok=0;
if(s[t]=='-') ok=1;
while(s[t]!=' '&&s[t]!='\n')
x=x*10+s[t]-'0',++t;
if(ok==1)
x=x*-1;
++t;
return x;
}
int main()
{
f>>n>>k;
Front=1;Back=0;f.get();
f.getline(s,2000000);l=strlen(s);
for(i=0;i<l;i++)
{
if(s[i]==' ')
{
if(ok==1)
a[++j]=-nr;
else
a[++j]=nr;
nr=0; ok=0;
}
else
if(s[i]=='-')ok=1;
else
nr=nr*10+s[i]-'0';
}
if(ok==1)a[n]=-nr;else a[n]=nr;
Max=-10000000;
for(i=1;i<=n;++i){
while(Front<=Back&&a[i]<a[dq[Back]])
--Back;
dq[++Back]=i;
if(dq[Front]==i-k)
++Front;
if(a[dq[Front]]>Max&&i>=k)
{
Max=a[dq[Front]];
in=i-k+1;
sf=i;
}
}
g<<in<<" "<<sf<<" "<<Max;
return 0;
}