Cod sursa(job #301498)

Utilizator HaggisRanca Razvan Haggis Data 8 aprilie 2009 11:37:27
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 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;
struct gigi{int nr; int l;}v[265000];

void updatare(int nod, int left, int right)
{
	if(pos==left && pos==right)
		{
			v[nod].nr=val;
			v[nod].l=1;
			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].nr))
	{	if(v[2*nod+1].nr>v[2*nod].nr)
			v[nod].l+=v[2*nod].l+v[2*nod+1].l;
							
		else
			{
				v[nod].l+=v[2*nod+1].l;
				v[2*nod].nr=0;
			}
		v[nod].nr=v[2*nod+1].nr;
	}
			
	else
		{if(v[2*nod+1].nr && nod!=1)
			{if(v[2*nod+1].nr>v[2*nod].nr)
				{
					if(v[2*nod].nr>v[nod-1].nr)
				{
					v[nod].nr=v[2*nod+1].nr;
					v[nod].l+=v[2*nod+1].l+v[2*nod].l;
				}
					else
						{if(v[2*nod+1].nr>v[nod-1].nr)
						{
							v[nod].nr=v[2*nod+1].nr;
							v[nod].l+=v[2*nod+1].l;
							v[2*nod].nr=0;
						}
						else
							{
								v[nod].nr=v[2*nod+1].nr;
								v[nod].l+=v[2*nod+1].l+v[2*nod].l;
								v[2*nod].nr=0;
							}
						}
				}
			else
			{
					v[nod].nr=v[2*nod+1].nr;
					v[nod].l=v[2*nod+1].l;
			}
			}
		else
			if(v[2*nod+1].nr)
			{
				v[nod].nr=max(v[2*nod+1].nr,v[2*nod].nr);
				v[nod].l+=v[2*nod].l+v[2*nod+1].l;
			}
		}
}
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=n;i<2*n;i++)
			s.insert(v[i].nr);
			
		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;
}