Pagini recente » Cod sursa (job #1583380) | Cod sursa (job #398) | Cod sursa (job #3293139) | Cod sursa (job #1185717) | Cod sursa (job #972525)
Cod sursa(job #972525)
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
struct Element{
int value;
int begin;
};
int minimum_result[21][500002],log[500002],Arr[500002],N,K;
Element Secv[500002];
void Calculate_log2()
{
int i=2,next=2;
while(i<=N)
{
if(i!=next)
log[i]=log[i-1];
else
{
log[i]=log[i-1]+1;
next=i*2;
}
i++;
}
}
void Read()
{
f>>N>>K;
int i;
for(i=1;i<=N;i++)
{
f>>Arr[i];
minimum_result[0][i]=Arr[i];
}
}
void Build_matrichs()
{
int i,j,forward=1;
for(i=1;i<=log[N];i++)
{
for(j=1;j<=N-forward*2+1;j++)
minimum_result[i][j]=min(minimum_result[i-1][j],minimum_result[i-1][j+forward]);
forward*=2;
}
}
int power(int x,int y)
{
int i,p=1;
for(i=1;i<=y;i++)
p*=x;
return(p);
}
int RMQ(int x,int y)
{
int i;
int how_much=log[y-x+1];
if(log[y-x]==how_much-1)
return minimum_result[log[y-x+1]][x];
else
return min(minimum_result[how_much][x],minimum_result[how_much][y-power(2,how_much)+1]);
}
void Solve()
{
int i=1,sum,maximum=-30001;
Secv[K].value=RMQ(1,K);
Secv[K].begin=1;
i=K+1;
while(i<=N)
{
if(RMQ(Secv[i-1].begin,i)<RMQ(i-K+1,i))
{
Secv[i].value=RMQ(i-K+1,i);
Secv[i].begin=i-K+1;
}
else
{
Secv[i].value=RMQ(Secv[i-1].begin,i);
Secv[i].begin=Secv[i-1].begin;
}
i++;
}
int result_begin,result_end;
for(i=K;i<=N;i++)
{
if(maximum<Secv[i].value)
{
maximum=Secv[i].value;
result_begin=Secv[i].begin;
result_end=i;
}
}
g<<result_begin<<" "<<result_end<<" "<<maximum<<"\n";
}
int main()
{
Read();
Calculate_log2();
Build_matrichs();
Solve();
return 0;
}