Cod sursa(job #48037)

Utilizator TheCreeepIonita Andrei Lucian TheCreeep Data 4 aprilie 2007 12:54:39
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
int x[1<<19],n,m,i,j, max, maxi;
int q[1<<19],a,b;
char s[1<<23];
int k;
int main (void)
{
	int t;
	max=-999999;
	q[0]=-999999;
	FILE *f=fopen("secventa.in","r");
	fscanf(f,"%d %d\n",&n,&m);
	fgets(s, 1<<23, f);
	a=1;	
	k=1;
	m=1;
	for(i=0;s[i]!='\n';i++)
	{
		if (s[i]=='-') m=-1; else
		if (s[i]==' ') 
		{
			x[k]*=m;
			k++; 
			m=1;			
		}else
		x[k]=x[k]*10+s[i]-'0';		
	}
	for(i=1;i<=m;++i)
	{
		while (q[b]>x[i]) b--;
		q[++b]=x[i];					
	}
	max=q[a];
	maxi=m;
	for(i=m+1;i<=n;++i)
	{
		{
			while (q[b]>x[i]) b--;
			q[++b]=x[i];
		}
		if (x[i-m]==q[a]) q[a++]=-999999;
		if (q[a]>max)
		{
			max=q[a];
			maxi=i;
		}
	}
	fclose(f);
	f=fopen("secventa.out","w");
	fprintf(f,"%d %d %d\n",maxi-m+1,maxi,max);
	fclose(f);	
	return 0;
}