Cod sursa(job #287531)

Utilizator laserbeamBalan Catalin laserbeam Data 24 martie 2009 22:23:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<deque>
using namespace std;
//struct node
//{
//	int val,poz;
//	node *next,*prev;
//};
//typedef struct node *lista;

deque<int> val;
deque<int> poz;

/*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()
{
ifstream f("secventa.in");
long i,n,k,c,max1,dr,st;
dr=st=0;
f>>n>>k;
//lista first,last;
//first=last=NULL;
for (i=1;i<k;i++)
{
	f>>c;
	while (val.size()>0 && val.back()>c)
	{
		val.pop_back();
		poz.pop_back();
	}
//	while (last && last->val >= c)deleteendnode(last);
//	addnode(first,last,c,i);
	val.push_back(c);
	poz.push_back(i);
}
max1=-30020;
for (i=k;i<=n;i++)
{
	f>>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;}
	if (poz.size()>0 && poz.front() == i-k)
	{
		poz.pop_front();
		val.pop_front();
	}
	while (val.size()>0 && val.back()>c)
	{
		val.pop_back();
		poz.pop_back();
	}
	val.push_back(c);
	poz.push_back(i);
	if (max1 < val.front()){max1=val.front(); dr=i; st=i-k+1;}
	
}
f.close();
ofstream g("secventa.out");
g<<st<<' '<<dr<<' '<<max1<<'\n';
g.close();

return 0;
}