# Cod sursa(job #632464)

Utilizator Data 11 noiembrie 2011 10:48:32 Secventa 100 cpp done Arhiva de probleme 1.47 kb
``````#include <cstdio>
#include <string.h>

using namespace std;

#define MAX_N 500005
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define LIM 3300000
#define INF 35000

short int A[MAX_N];
int Deq[MAX_N];
int li=1,lf,N,i,K;
int BEST = -INF;
int In, Out;
char sir[LIM];

{
int x,ind,i=0,sem=1;
fgets(sir, LIM, stdin); x = ind = 0;
int L=strlen(sir);
for (ind=0; ind<=L; ++ind)
{
if (sir[ind]==' ' || sir[ind]=='\n')
{
if (sem==1) A[++i]=x; else A[++i]=-x;
sem=1;
x=0;
}
if (sir[ind]=='-') sem=-1;
if (sir[ind]>='0' && sir[ind]<='9')
x = x*10+(sir[ind]-'0');
}
}

void Deqin (int x)
{
Deq[++lf]=x;
if (A[x]<A[Deq[li]]) {  Deq[li]=x; lf=li; }
while (A[Deq[lf]]<A[Deq[lf-1]] && lf>li)
{ Deq[lf-1]=Deq[lf]; lf--; }
while (x-Deq[li]>=K) ++li;
}

int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf ("%d %d\n" , &N, &K);

for (i=1; i<=N; ++i)
{
Deqin(i);
if (A[Deq[li]]>BEST && i>K-1)
{
BEST=A[Deq[li]]; In=i-K+1; Out=i;
}
}

printf("%d %d %d\n",In, Out, BEST);
return 0;
}
``````