Cod sursa(job #66981)

Utilizator nuexistnuexist nuexist Data 21 iunie 2007 23:36:56
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
int n,i,a[500001],coada[500001],prim,ultim,max,min,pozmax,pos[500001],k;
int main()
{
	fscanf(f,"%d %d",&n,&k);
	for(i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
	fclose(f);
	
	prim=ultim=1;
	coada[1]=a[1];
	pos[1]=1;
	max=a[i];
	pozmax=1;
	for(i=2;i<=n-k+1;i++)
	{
		if(coada[prim]<a[i]){
			prim++;
			if(a[i]<ultim&&i-pos[ultim]<k) ultim--;
			coada[++ultim]=a[i];
			pos[ultim]=i;
			if(i!=n-k+1) {max=a[i];pozmax=pos[prim];}
		}
	}
	min=a[n-k+1];
	for(i=n-k+2;i<=n;i++)
		if(min>a[i]) min=a[i];
	if(min>max) {max=min;
		         pozmax=n-k+1;}
	
	fprintf(g,"%d %d %d\n",pozmax,pozmax+k-1,max);
	fclose(g);
	return 0;
}