Cod sursa(job #333155)

Utilizator dodgerblueBogdan P. dodgerblue Data 21 iulie 2009 16:35:40
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<stdio.h>
#include<stdlib.h>

int main()
{
	FILE *f,*g;
	int n,k,i,a[500000];
	int start,end,Q[1000],poz,max=-9999999;
	
	f=fopen("secventa.in","r");
	g=fopen("secventa.out","w");
	
	fscanf(f,"%d %d\n",&n,&k);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	
	start=1;
	end=0;
	
	for(i=1;i<=n;i++)
	{
		while(start<=end && Q[start]<=i-k) start++;
		while(start<=end && a[Q[end]]>a[i]) end--;
		Q[++end]=i;
		if(a[Q[start]]>max && i>=max)
		{
			max=a[Q[start]];
			poz=i;
		}
	}
	
	fprintf(g,"%d %d %d\n",poz-k+1,poz,max);
	
	fclose(f);
	fclose(g);
	return 0;
}