Cod sursa(job #330278)

Utilizator ZethpixZethpix Zethpix Data 9 iulie 2009 13:21:02
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <stdio.h>
FILE *f,*g;
int n,k,i,st,dr,rez,poz,a[500000],q[500000];
int main(){
	f=fopen("secventa.in","r");
	g=fopen("secventa.out","w");
	fscanf(f,"%d%d",&n,&k);
	for (i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	rez=0;
	st=1;dr=0;
	for (i=1;i<=k-1;i++){
		while (dr>=st&&a[i]<=a[q[dr]]) dr--;
		dr++;
		q[dr]=i;
	}
	for (i=k;i<=n;i++){
		while (st<=dr&&a[i]<=a[q[dr]]) dr--;
		dr++;
		q[dr]=i;
		while (st<=dr&&q[st]<i-k+1) st++;
		if (a[q[st]]>rez){
			rez=a[q[st]];
			poz=i;
		}
	}
	fprintf(g,"%d %d %d\n",poz-k+1,poz,rez);
	fclose(f);
	fclose(g);
	return 0;
}