Pagini recente » Borderou de evaluare (job #1961566) | Istoria paginii runda/parfum_de_iasomnie | Borderou de evaluare (job #2157649) | Cod sursa (job #2937431) | Cod sursa (job #2306451)
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
#define maxn 500000
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n, k, maxim=-30001, v[maxn+2], pos;
int dq[maxn+2], fr=1, bk=0, posi, posj;
string s;
int main()
{
fin>>n>>k;
fin.get();
getline(fin,s);
for(int i=0; i<s.size(); i++)
{
int t=0;
if(s[i]=='-')
{
i++;
while(s[i]>='0'&&s[i]<='9')
{
t=t*10+('0'-s[i]);
i++;
}
v[++pos]=t;
}
else if('0'<=s[i]&&s[i]<='9')
{
while('0'<=s[i]&&s[i]<='9')
{
t=t*10+(s[i]-'0');
i++;
}
v[++pos]=t;
}
}
for(int i=1; i<=k; i++)
{
if(v[i]<=v[dq[fr]])
{
bk=fr;
dq[bk]=i;
}
else if(v[dq[bk]]<v[i])
{
dq[++bk]=i;
}
else
{
int st=fr, dr=bk, mid;
while(st<dr)
{
mid=(st+dr)/2;
if(v[dq[mid]]<v[i])
{
st=mid+1;
}
else
{
dr=mid;
}
}
mid=(st+dr)/2;
if(v[dq[mid]]>=v[i]) mid--;
bk=mid;
dq[++bk]=i;
}
//while(fr<=bk&&v[i]<=v[dq[bk]]) bk--;
}
if(maxim<v[dq[fr]])
{
maxim=v[dq[fr]];
posj=1;
posi=k;
}
for(int i=k+1; i<=n; i++)
{
if(v[i]<=v[dq[fr]])
{
bk=fr;
dq[bk]=i;
}
else if(v[dq[bk]]<v[i])
{
dq[++bk]=i;
}
else
{
int st=fr, dr=bk, mid;
while(st<dr)
{
mid=(st+dr)/2;
if(v[dq[mid]]<v[i])
{
st=mid+1;
}
else
{
dr=mid;
}
}
mid=(st+dr)/2;
if(v[dq[mid]]>=v[i]) mid--;
bk=mid;
dq[++bk]=i;
}
//while(fr<=bk&&v[i]<=v[dq[bk]]) bk--;
if(i-dq[fr]>=k)
{
fr++;
}
if(maxim<v[dq[fr]])
{
maxim=v[dq[fr]];
posi=i;
posj=i-k+1;
}
}
fout<<posj<<' '<<posi<<' '<<maxim<<'\n';
return 0;
}