Pagini recente » Cod sursa (job #2914459) | Cod sursa (job #1602963) | Cod sursa (job #110054) | Cod sursa (job #58987) | Cod sursa (job #2122725)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int N,V[500003],P[20]= {0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144},K,Max=-10000000,Poz1,Poz2;
vector < int > Min[20];
char Sir[3500000];
int main()
{
fin>>N>>K;
fin.getline(Sir,300);
fin.getline(Sir,sizeof(Sir));
int Semn=1,Dim=1;
for(int i=0;Sir[i]!=0;i++)
{
if(Sir[i]==' ')
{
V[Dim]=Semn*V[Dim];
Dim++;
Semn=1;
}
if(Sir[i]=='-')
Semn=-1;
if(Sir[i]>='0' && Sir[i]<='9')
V[Dim]=V[Dim]*10+Sir[i]-'0';
}
V[N]=V[N]*Semn;
for(int i=1; i<=N-1; i++)
Min[1].push_back(min(V[i],V[i+1]));
for(int i=2; i<=18; i++)
{
if(N-P[i]+1<0)
break;
for(int j=0; j<N-P[i]+1; j++)
Min[i].push_back(min(Min[i-1][j],Min[i-1][j+P[i]/2]));
}
if(K==1)
{
for(int i=1; i<=N; i++)
if(V[i]>Max)
{
Max=V[i];
Poz1=i;
}
fout<<Poz1<<" "<<Poz1<<" "<<Max<<"\n";
}
else
{
int Search;
for(int i=1; i<=18; i++)
if(K>=P[i])
Search=i;
for(int i=1; i<=N-K+1; i++)
if(min(Min[Search][i-1],Min[Search][i+K-P[Search]-1])>Max)
{
Poz1=i;
Max=min(Min[Search][i-1],Min[Search][i+K-P[Search]-1]);
}
fout<<Poz1<<" "<<Poz1+K-1<<" "<<Max<<'\n';
}
}