Pagini recente » Cod sursa (job #2232436) | Cod sursa (job #3135684) | Cod sursa (job #1894086) | Cod sursa (job #977452) | Cod sursa (job #972559)
Cod sursa(job #972559)
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int Deque[500003],N,K,Arr[500003],Begin,End;
int Secv[500003];
long long sum;
void read()
{
f>>N>>K;
int i;
for(i=1;i<=N;i++)
f>>Arr[i];
}
void calculate()
{
int i,maximum=-32001,end;
Begin=1;End=0;
for(i=1;i<=K;i++)
{
while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
End--;
Deque[++End]=i;
}
Secv[K]=Arr[Deque[Begin]];
if(Secv[K]>maximum)
{
maximum=Secv[K];
end=K;
}
for(i=K+1;i<=N;i++)
{
while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
End--;
Deque[++End]=i;
if(Deque[Begin]==i-K)
Begin++;
Secv[i]=Arr[Deque[Begin]];
if(Secv[i]>maximum)
{
maximum=Secv[i];
end=i;
}
}
g<<end-K+1<<" "<<end<<" "<<maximum<<"\n";
}
/*void print()
{
int i,maximum=-32001,end;
for(i=K;i<=N;i++)
{
if(Secv[i]>maximum)
{
maximum=Secv[i];
end=i;
}
}
g<<end-K+1<<" "<<end<<" "<<maximum<<"\n";
}*/
int main()
{
read();
calculate();
return 0;
}