Cod sursa(job #275821)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 18:08:11
Problema Secventa Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
#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(i==k+d[p]) //trebuie scos primul element din deque
			p++; //il scoatem
		if(i>=k&&v[d[p]]>bmax) //a gasit una de baza mai mare
			{
			bmax=v[d[p]]; //salvam baza maxima
			pi=i-k+1; ps=i; //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;
}