Pagini recente » Cod sursa (job #2968120) | Cod sursa (job #508613) | Cod sursa (job #2137875) | Cod sursa (job #1234535) | Cod sursa (job #253153)
Cod sursa(job #253153)
include<fstream>
using namespace std;
int a[500009];
int b[500009];
int main(){
int n, k, i, vf, ult,x,pi,psf,bmax, pas,tz;
ifstream f("secventa.in");
f>>n>>k;
vf=0;
ult=-1;
for(i=0;i<k;i++){
f>>x;
for(pas=1;pas<=ult;pas<<=1);
for(tz=vf-1;pas;pas>>=1)
if(a[tz+pas]<x && tz+pas<=ult)
tz+=pas;
ult=tz;
if(ult<vf)
ult=vf=0;
else
++ult;
a[ult]=x;
b[ult]=i+1;
}
pi=1;psf=k;bmax=a[vf];
for(i=k+1;i<=n;i++){
if(b[vf]<i-k+1) vf++;
f>>x;
for(pas=1;vf+pas<ult+2;pas<<=1);
for(tz=vf-1;pas;pas>>=1)
if(a[tz+pas]<x && tz+pas<=ult)
tz+=pas;
ult=tz;
if(ult<vf)
ult=vf;
else ++ult;
a[ult]=x;
b[ult]=i;
if(a[vf]>bmax){bmax=a[vf];psf=i;pi=i-k+1;}
}
f.close();
ofstream g("secventa.out");
g<<pi<<' '<<psf<<' '<<bmax<<'\n';
g.close();
return 0;
}