Cod sursa(job #287506)

Utilizator laserbeamBalan Catalin laserbeam Data 24 martie 2009 22:08:36
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<cstdio>
using namespace std;
struct node
{
	int val,poz;
	node *next,*prev;
};
typedef struct node *lista;

void addnode(lista &first, lista &last, int x, int y)
{
	node *p = new node;
	p->val=x;
	p->poz=y;
	p->next=NULL;
	if (!first)first=p;
	if (last){last->next=p;p->prev=last;}
	else p->prev = NULL;
	last=p;
}
void deletestartnode(lista &first)
{
	node *p;
	p=first;
	first=first->next;
	delete p;
}
void deleteendnode(lista &last)
{
	node *p;
	p=last;
	last=last->prev;
	delete p;
}

int main()
{
FILE *f;
f=fopen("secventa.in","r");
long i,n,k,dr,st;
int c,max1;
dr=st=0;
fscanf(f,"%ld %ld",&n,&k);
lista first,last;
first=last=NULL;
for (i=1;i<k;i++)
{
	fscanf(f,"%d ",&c);
	while (last && last->val >= c)deleteendnode(last);
	addnode(first,last,c,i);
}
max1=-30020;
for (i=k;i<=n;i++)
{
	fscanf(f,"%d ",&c);
	if (first->poz == i-k)deletestartnode(first);
	while (last && last->val >= c)deleteendnode(last);
	if (!last)first=NULL;
	addnode(first,last,c,i);
	if (max1 < first->val){max1=first->val; dr=i; st=i-k+1;}

	
}
fclose(f);
f = fopen("secventa.out","w");
fprintf(f,"%ld %ld %d\n",st,dr,max1);
fclose(f);

return 0;
}