Cod sursa(job #275791)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 17:53:02
Problema Secventa Scor 0
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(d[q]-d[p]==k) //secventa are lungimea ceruta
			{
			p++; //inaintam
			if(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;
}