Pagini recente » Cod sursa (job #676748) | Cod sursa (job #768277) | Cod sursa (job #1612726) | Cod sursa (job #1655920) | Cod sursa (job #211696)
Cod sursa(job #211696)
#include <deque>
#include <stdio.h>
#define MAX 500000
using namespace std;
deque <int> coada;
int sir[MAX],n,k;
int start,max_min;
void citire()
{
scanf ("%d %d",&n,&k);
char ca[MAX*10],c;
int j=0;
int semn;
scanf ("%c",&c);
fgets(ca,MAX*10,stdin);
for (int i=0;i<n;i++)
{
semn=0;
sir[i]=0;
while(ca[j]!='-' && (ca[j]<'0' || ca[j]>'9'))
j++;
if(ca[j]=='-')
{
semn=1;
j++;
}
while(ca[j]>='0' && ca[j]<='9')
{
sir[i]=sir[i]*10+(ca[j]-'0');
j++;
}
if(semn)
sir[i]=-sir[i];
}
}
void solve()
{
start=0;
for (int i=0;i<k;i++)
{
while (!coada.empty() && sir[coada.back()]>=sir[i])
coada.pop_back();
coada.push_back(i);
}
max_min=sir[coada.front()];
for (int i=k;i<n;i++)
{
if (coada.front()==i-k)
coada.pop_front();
while(!coada.empty() && sir[coada.back()]>=sir[i])
coada.pop_back();
coada.push_back(i);
if (sir[coada.front()]>max_min)
{
max_min=sir[coada.front()];
start=i-k+1;
}
}
}
void afisare()
{
//fout<<start+1<<" "<<start+k<<" "<<max_min<<"\n";
printf("%d %d %d\n",start+1,start+k,max_min);
}
int main ()
{
freopen ("secventa.in","r",stdin);
freopen ("secventa.out","w",stdout);
citire();
solve();
afisare();
return 0;
}