Cod sursa(job #275847)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 18:21:18
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
#define infile "secventa.in"
#define outfile "secventa.out"
#define nmax 500*1001
#define lmax nmax*7
char x[lmax]; //vectorul in care citim numerele ca sir de caractere
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,j,s;
	scanf("%d %d\n",&n,&k);
	fgets(x,lmax,stdin); //citim sirul cu nele n numere
	//parsam citirea
	for(i=1,j=0;i<=n;i++) //trebuie sa facem cele n numere
		{
		while(x[j]==' ') j++;
		if(x[j]=='-') { s=1; j++; } else s=0; //sa stim daca numarul este negativ zau pozitiv
		while(x[j]>='0'&&x[j]<='9') v[i]=v[i]*10+x[j++]-'0'; //reconstituim numarul;))
		if(s) v[i]*=-1; //avem nr negativ
		}
	}

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;
}