Cod sursa(job #47977)

Utilizator TheCreeepIonita Andrei Lucian TheCreeep Data 4 aprilie 2007 12:01:56
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>
int x[1<<19],n,m,i,j, max, maxi;
class dequeue{
	public:
	int a, b, q[1<<19];
	void pop()
	{
		a++;
	}
	void push(int X)
	{
		while (b>0 && q[b]>X) b--;
		q[++b]=X;		
	}
	int top()
	{
		return q[a];
	}
	void init()
	{
		a=1;
		b=0;
	}
};
int main (void)
{
	FILE *f=fopen("secventa.in","r");
	fscanf(f,"%d %d",&n,&m);
	class dequeue dq;
	dq.init();
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%d",&x[i]);
		dq.push(x[i]);
		if (i-m>0 && x[i-m]==dq.top()) dq.pop(); 
		if (dq.top()>max)
		{
			max=dq.top();
			maxi=i;
		}
	}
	fclose(f);
	f=fopen("secventa.out","w");
	fprintf(f,"%d %d %d\n",maxi-m+1,maxi,max);
	fclose(f);
	
	return 0;
}