Cod sursa(job #605820)

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

typedef unsigned long miu;

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

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

void push (int 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 plocal->pprev->pnext=plocal;
	contor++;
}

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

int main ()
{
	ifstream fin;
	fin.open ("secventa.in");
	miu N, K, i;
	int 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->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;
}