Pagini recente » Cod sursa (job #86121) | Cod sursa (job #1442006) | Cod sursa (job #2083834) | Cod sursa (job #2107185) | Cod sursa (job #374571)
Cod sursa(job #374571)
#include<iostream>
#include<fstream>
using namespace std;
const int N=3500000;
ifstream f("secventa.in");
ofstream g("secventa.out");
int dq[500001];
int v[500001];
int n,k,i,st,dr;
char t[N];
inline void stanga(int i)
{
if(dq[st]==i-k)
++st;
}
void dreapta(int i)
{
while (st<=dr&&v[i] <= v[dq[dr]] )
--dr;
dq[++dr]=i;
}
int main()
{
f>>n>>k>>ws;
int i1,i2,semn=1,x=0,nr=0,max=0;
st=1; dr=0;
f.getline(t,N);
for(i=0; t[i]&&t[i]!='\n';++i)
{
if(t[i]=='-')
{
semn=-1;
continue;
}
if(t[i]==' ')
{
v[++nr]=x*semn;
x=0;semn=1;
continue;
}
x=x*10+t[i]-'0';
}
if(nr!=n)
v[++nr]=x*semn;
for(i=1; i<=k; i++)
dreapta(i);
i2=k;
i1=1;
max=v[dq[st]];
for(i=k+1; i<=n; i++)
{
stanga(i);
dreapta(i);
if (v[dq[st]]>max)
{
max=v[dq[st]];
i2=i;
i1=i-k+1;
}
}
g<<i1<<" "<<i2<<" "<<max;
return 0;
}