Cod sursa(job #969674)

Utilizator bugyBogdan Vlad bugy Data 4 iulie 2013 23:53:08
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <stdio.h>
#define dim 500005

struct lista_elem {
    int value;
	int index;
	struct lista_elem *next,*prev;
};

class LinkedList {
   
	public: 
	/** Definiti membrii de care am nevoie*/
		
	struct lista_elem *pfirst,*plast,*paux,*pp,*p;
	int ok;
    
	void add(int nr,int ind) 
	{	

	paux = new struct lista_elem;
    paux -> value = nr;
    paux -> index = ind;
	
	if(pfirst == NULL) /**Daca n-am niciun numar in lista*/
	{
		paux->next = NULL;
		paux->prev = NULL;
		pfirst = paux; 
		plast = paux;		
	}
	else
	{
		if(pfirst -> next == NULL) /**Daca am doar un nod in lista*/
		{
			if( pfirst->value < nr )
			{
				paux->next = NULL;
				paux->prev = pfirst;
				pfirst->next = paux;
				plast = paux;
			}
			else 
			{
				pfirst->prev = paux;
				paux->next = pfirst;
				pfirst = paux;	
				plast = pfirst->next;
			}
				
		}
		else	 /**Daca am mai multe numere in lista*/
		{
			if( pfirst->value >= nr )
			{
				paux->next = pfirst;
				pfirst->prev = paux;
				pfirst = paux;	
			}
			else 
			{
				pp = pfirst;
				p =  pfirst->next;
				ok = 0;
				while(p != NULL)
				{
					if( p->value < nr ) 
					{
						pp = p;
						if(p->next != NULL)
						{
							p = p->next;
							continue;
						}
						else break;
					}
					else 
					{
						paux->next = p;
						p->prev = paux;
						paux->prev = pp;
						pp->next = paux; 						
						ok = 1;
						break;
					}
					
				pp = p;
				p = p->next;
				}
				
				if(!ok)
				{
					paux->next = NULL;
					paux->prev = pp;
					pp->next = paux;
					plast = paux;
				}
			}
		}
	}	
	}
	
	void addLast(int x, int ind) 
	{
            struct lista_elem *paux;

            paux = new struct lista_elem;
            paux->value = x;
            paux->index = ind;
			
            paux->prev = plast;
            paux->next = NULL;

            if (plast != NULL)	plast->next = paux;
            plast = paux;
            if (pfirst == NULL)	pfirst = plast;
	}
	
	void del(int x)
	{
		p = plast;
		while(p != NULL)
		{
			if(p->value >= x)
			{
				if(p->prev != NULL)
 					p->prev->next = NULL;
				pp = p->prev;
				plast = pp;
				delete p;
				p = pp;
			}
			else break;		
		}	
	}
	
	void remove(int ind)
	{
		while(pfirst != NULL)
		{
			if(pfirst->index < ind)
			{
				if(pfirst->next != NULL)
					pfirst->next->prev = NULL;
				else plast = NULL;
				p = pfirst;
				pfirst = pfirst->next;
				delete p;
			}	
			else break;
		}		
	}
	
    LinkedList()
	{
		pfirst = NULL;
		plast = NULL;
	}
   ~LinkedList(){}  
};

void citire(int *in,int *sf, int *min)
{
	int i,N,K,x;
	
	LinkedList Deque;
	
	FILE *f=fopen("secventa.in","r");
	
	fscanf(f,"%d %d",&N,&K);
	
	//citim primele K numere
	for(i = 1; i <=  K; i++)
	{
		fscanf(f,"%d",&x);
		Deque.add(x,i);
		if(x < *min)
		{
			*min = x;
		}
	}
		
	//initializam prima secventa
	*in = 1;
	*sf = K;
	//cautam secvente mai bune
	for(i = K + 1; i <= N; i++)
	{
		fscanf(f,"%d",&x);
		//stergem de la coada numerele mai mari decat x
		Deque.del(x);	
		//stergem de la cap numerele care depasesc secventa
		Deque.remove(i-K+1);	
		//adaugam la coada x
		Deque.addLast(x,i);
	
		if(Deque.pfirst->value > *min)
		{
			*min = Deque.pfirst->value;
			*in = i - K + 1;
			*sf = i;
		}
	}
	
fclose(f);
}

void afisare(int in,int sf, int min)
{
	FILE *g = fopen("secventa.out","w");	
	fprintf(g,"%d %d %d\n", in, sf, min);
fclose(g);
}

int main()
{
	int in, sf, min;
	
	citire(&in, &sf, &min);
	afisare(in,sf,min);
	

return 0;
}