Pagini recente » Istoria paginii runda/concurs_11_12_02_26 | Atasamentele paginii Clasament paranteze | Cod sursa (job #2350693)
#include <cstdio>
#include <deque>
#define NMAX 500000
using namespace std;
deque <int> val;
deque <int> poz;
int v[NMAX+5];
int main()
{
int nmax,l,pozi,n,k,i,nr,lmax;
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
if(i<=k)
{
while(!val.empty()&&v[i]<val.back())
{
val.pop_back();
poz.pop_back();
}
val.push_back(v[i]);
nr=val.back();
poz.push_back(i);
}
}
nmax=val.front();
l=lmax=k;
nr=val.front();
pozi=k;
for(i=k+1;i<=n;i++)
{
while(!val.empty()&&val.back()>v[i])
{
poz.pop_back();
val.pop_back();
}
val.push_back(v[i]);
poz.push_back(i);
while(!poz.empty()&&poz.back()-poz.front()+1>k)
{
poz.pop_front();
val.pop_front();
}
if(val.front()==nr)
l++;
else
{
if(nr>nmax)
{
lmax=l;
nmax=nr;
pozi=i;
}
nr=val.front();
l=k;
}
}
if(nr>nmax)
{
lmax=l;
nmax=nr;
pozi=n;
}
printf("%d %d %d",pozi-lmax+1,pozi,nmax);
return 0;
}