Cod sursa(job #97769)

Utilizator piroslPiros Lucian pirosl Data 8 noiembrie 2007 18:17:59
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
#include <stdlib.h>

class nod
{
public:
	int value;
	class nod* prev;
	class nod* next;
	nod()
	{
		prev = 0;
		next = 0;
	}
};

nod* noduri[500001];

nod* head;

void adauga(nod* value)
{
	if(head == 0)
		head = value;
	else
	{
		if(value->value <= head->value)
		{
			head->prev = value;
			value->next = head;
			head = value;
		}
		else
		{
			nod* tmp = head;
			while(tmp->value < value->value && tmp->next != 0)
				tmp = tmp->next;
			if(tmp->value < value->value)
			{
				tmp->next = value;
				value->prev = tmp;
			}
			else
			{
				tmp->prev->next = value;
				value->prev = tmp->prev;
				value->next = tmp;
				tmp->prev = value;
			}
		}
	}
}

void print()
{
	nod *tmp = head;
	while(tmp != 0)
	{
		printf("%d ", tmp->value);
		tmp = tmp->next;
	}
	printf("\n");
}

void sterge(nod* value)
{
	if(value == head)
	{
		head = value->next;
		if(head != 0)
			head->prev = 0;
		delete value;
		return;
	}
	if(value->next == 0)
	{
		value->prev->next = 0;
		delete value;
		return;
	}
	value->prev->next = value->next;
	value->next->prev = value->prev;
	delete value;
}

int main(void)
{
	FILE* fin;
	FILE* fout;
	fin = fopen("secventa.in", "r");
	fout = fopen("secventa.out", "w");
	int n, k;
	head = 0;
	fscanf(fin, "%d %d\n", &n, &k);

	int max = -30001;
	int start = -1;

	for(int i=0;i<n;++i)
	{
		int v;
		fscanf(fin, "%d ", &v);
		noduri[i] = new nod();
		noduri[i]->value = v;
		adauga(noduri[i]);
		if(i>=k-1)
		{
			//print();
			//values[i-(k-1)] = head->value;
			if(head->value > max)
			{
				max = head->value;
				start = i-(k-1);
			}
			sterge(noduri[i-(k-1)]);
		}
	}
	//for(int i=0;i<n-(k-1);++i)
	//{
	//	printf("%d ", values[i]);
	//	if(values[i] > max)
	//	{
	//		max = values[i];
	//		start = i;
	//	}
	//}
	fclose(fin);
	fprintf(fout, "%d %d %d\n", start+1, start+1+k-1, max);
	fclose(fout);
	return 0;
}