Cod sursa(job #605830)

Utilizator SteveStefan Eniceicu Steve Data 2 august 2011 12:56:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream.h>

typedef long miu;

typedef struct numar
{
	miu nr;
	miu pozitie;
	numar *pprev, *pnext;
};

numar *f=NULL, *l=NULL;
miu max=-30001;
miu fata=0, spate=0;
numar element;
miu contor=0;

void push (miu a, miu j)
{
	numar *plocal=new numar;
	plocal->nr=a;
	plocal->pozitie=j;
	plocal->pprev=l;
	plocal->pnext=NULL;
	l=plocal;
	if (f == NULL) f=plocal;
	else
	{
		if (l->pprev != NULL) l->pprev->pnext=l;
	}
	contor++;
}

void pop_back ()
{
	memcpy (&element, f, sizeof (numar));
	delete f;
	if (element.pnext == NULL) l=NULL;
	else
	{
		f=element.pnext;
		f->pprev=NULL;
	}
	contor--;
}

int main ()
{
	ifstream fin;
	fin.open ("secventa.in");
	miu N, K, i;
	miu b, minim=30001;
	fin>>N>>K;
	for (i=1; i<=N; i++)
	{
		fin>>b;
		push (b, i);
		if (contor > K)
		{
			pop_back ();
			if (element.nr > max)
			{
				max=element.nr;
				fata=element.pozitie;
				spate=fata+K-1;
			}
		}
		if (l->pprev != NULL)
		{
			if (l->nr < l->pprev->nr)
			{
				miu poz=f->pozitie;
				minim=f->nr;
				while (contor > 1)
				{
					pop_back ();
				}
				if (minim > l->nr)
				{
					minim=l->nr;
					poz=l->pozitie;
				}
				if (minim > max)
				{
					max=minim;
					fata=poz;
					if (fata+K-1 > N) spate=N;
					else spate=fata+K-1;
				}
			}
		}
	}
	if ((max < f->nr) && (contor > 1))
	{
		max=f->nr;
		fata=N-K+1;
		spate=N;
	}
	fin.close ();
	ofstream fout;
	fout.open ("secventa.out");
	fout<<fata<<" "<<spate<<" "<<max;
	fout.close ();
	return 0;
}