Pagini recente » Cod sursa (job #3002649) | Cod sursa (job #355201) | Cod sursa (job #1528729) | Cod sursa (job #1372598) | Cod sursa (job #275808)
Cod sursa(job #275808)
#include<stdio.h>
#define infile "secventa.in"
#define outfile "secventa.out"
#define nmax 500*1001
int v[nmax]; //vectorul cu numere
int d[nmax]; //deque=ul in care vom lucra
int n,k; //numarul de elemente din vector, respectiv dimensiunea minima a subsecventei
int p,q; //capetele deque-ului
int bmax=(-1)*(~(1<<31)); //baza maxima ;))
int pi,ps; //pozitia de inceput, si pozitia de sfarsit a secventei
void citire()
{
int i;
scanf("%d %d\n",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
}
void rezolvare()
{
int i;
p=1;q=0; //initial deque-ul este gol;))
for(i=1;i<=n;i++) //trecem pe la fiecare element al sirului
{
while(p<=q && v[d[q]]>=v[i]) q--; //este mai mare...deci nu ne mai intereseaza
d[++q]=i; //salvam pozitia elementului din sir
if(d[q]-d[p]==k) //secventa are lungimea ceruta
{
p++; //inaintam
}
if(i>=k&&v[d[p]]>bmax) //a gasit una de baza mai mare
{
bmax=v[d[p]]; //salvam baza maxima
pi=d[p]; ps=d[q]; //salvam capetele
}
}
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire();
rezolvare();
printf("%d %d %d\n",pi,ps,bmax);
fclose(stdin);
fclose(stdout);
return 0;
}