Cod sursa(job #264787)

Utilizator SheepBOYFelix Liviu SheepBOY Data 22 februarie 2009 19:10:04
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
struct DEQUE{
	short int v,p;
	DEQUE()
	{
		v=p=30001;
	}
};
int sq,eq;
DEQUE dq[1000000];
int v[500000];
int main()
{
	int i,j,n,k,minim=-30001,pm=30000;
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d %d",&n,&k);
	int nq=0;
	if(k>2)
	{
	while(nq<k-1)
	{
		scanf("%d",&v[nq]);
		j=sq;
		while(dq[j].v<v[nq])
			++j;
		dq[j].v=v[nq];
		dq[j].p=nq;
	++nq;
	}
	int cp=nq;
	nq=0;
	for(i=cp;i<n;++i)
	{
		scanf("%d",&v[i]);
		j=sq;
		while(dq[j].v<v[i])
			++j;
		dq[j].v=v[i];
		dq[j].p=i;
		eq=j;
		if(minim<dq[sq].v)
			{
				minim=dq[sq].v;
				pm=dq[sq].p;
			}
		if(i-dq[sq].p+1>=k)
			++sq;
	}
		if(minim<dq[sq].v)
			{
				minim=dq[sq].v;
				pm=dq[sq].p;
			}
	while(v[pm]>=minim)
		--pm;
	pm++;
	printf("%d %d %d",pm+1,pm+k,minim);
	}
	if(k==1)
	{
		for(i=0;i<n;++i)
		{
			scanf("%d",&v[i]);
			if(v[i]>minim)
			{
				minim=v[i];
				pm=i;
			}
		}
		printf("%d %d %d",pm+1,pm+1,minim);
	}
	if(k==2)
	{
		scanf("%d",&v[i]);
		for(i=1;i<n;++i)
		{
			scanf("%d",&v[i]);
			if(v[i]>minim)
			{
				minim=v[i];
				pm=i-1;
			}
			if(v[i-1]<v[i])
			{
				minim=v[i-1];
				pm=i-1;
			}
		}
		printf("%d %d %d",pm+1,pm+2,minim);
	}
		return 0;
}