Cod sursa(job #301680)

Utilizator HaggisRanca Razvan Haggis Data 8 aprilie 2009 13:01:31
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<fstream>
#include<algorithm>
#include<set>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int a[100001],n,i,j,val,pos,nrtot,poz[100001];
int v[265000];

void update1(int nod, int left, int right)
{
	v[nod]=0;
	if(!(v[2*nod]==0 && v[2*nod+1]==0))
		{
			update1(2*nod, left, (right+left)/2);
			update1(2*nod+1, (left+right)/2+1,right);
		}
}

void updatare(int nod, int left, int right)
{
	
	if(pos==left && pos==right)
		{
			v[nod]=val;
			poz[pos]=nod;
			return;
		}
	long long mij=(left+right)/2;
	if(pos<=mij)
		updatare(2*nod,left,mij);
	else
		updatare(2*nod+1,mij+1,right);
	if(nod%2==0 && (v[2*nod+1]))
	{	if(v[2*nod+1]<v[2*nod])
			update1(2*nod, left, (left+right)/2);
			
		v[nod]=v[2*nod+1];
	}
			
	else
		{if(v[2*nod+1] && nod!=1)
			{
				if(v[2*nod+1]>v[2*nod])
				
					if(v[2*nod]<v[nod-1] && v[2*nod+1]>v[nod-1])
						update1(2*nod, left, (left+right)/2);
						
				
			
			v[nod]=v[2*nod+1];
			}	
			
			
		else
			if(v[2*nod+1])
				v[nod]=max(v[2*nod+1],v[2*nod]);
				
			
		}
}
int main()
{
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>a[i];
		pos=i;
		val=a[i];
		updatare(1,1,n);
	}
	
		set<int> s;
		for(i=1;i<=n;i++)
			{
				s.insert(v[poz[i]]);
		}
			
		if(*s.begin()==0)
			out<<s.size()-1<<"\n";
		else
			out<<s.size()<<"\n";
			
			
		for(set<int>::iterator it=s.begin(); it!=s.end(); it++)
			if(*it)
				out<<*it<<" ";
	
	return 0;
}