Cod sursa(job #334370)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 26 iulie 2009 15:07:27
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>

int main()
{
	int coada[500000],i,n,k,x[500000],tail,head,max=-30001,pozmax;
	FILE *f=fopen("secventa.in","r");

	fscanf(f,"%i%i",&n,&k);
	for(i=0;i<n;i++)
		fscanf(f,"%i",x+i);
	fclose(f);

	tail=0;
	head=0;
	coada[0]=0;

	for(i=0;i<n;i++)
	{
		while(tail<=head && x[i]<x[coada[head]])
			head--;
		coada[head++]=i;

		if(i-k+1>coada[tail])
			tail++;
		if(i+1>=k)
		{
			if(x[coada[tail]]>max)
			{
				max=x[coada[tail]];
				pozmax=coada[tail];
			}
		}
	}

	f=fopen("secventa.out","w");
	if(pozmax+1>=k)
		fprintf(f,"%i %i %i\n",pozmax+1-k,pozmax+1,max);
	else
		fprintf(f,"%i %i %i\n",1,k,max);
	fclose(f);
	return 0;
}