Cod sursa(job #1138391)

Utilizator span7aRazvan span7a Data 9 martie 2014 22:44:28
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int k,n,i;
struct vec
{
	int val,poz;	
};
vec v[100001];
int s[100001];
struct cmp
{
	bool operator() (vec a,vec b)
	{
		if(a.poz<b.poz)return true;
		else return false;
	}
};
vector<vec>aux;
priority_queue<vec,vector<vec>,cmp>x;
int main()
{
	f>>n;
	for(i=1;i<=n;i++)
	{	f>>k;
		v[i].val=k;
		while(x.top().val>k&&x.size())
				{
					aux.push_back(x.top());
					x.pop();
				}
		if(x.top().val<k&&x.size())
		{
			vec a;
			a.val=k;
			a.poz=x.top().poz+1;
			
			v[i].poz=a.poz;
			x.push(a);
		}
		else 
		{
			vec a;
			a.val=k;
			a.poz=1;
			v[i].poz=a.poz;
			x.push(a);
		}
		while(aux.size())
		{
			x.push(aux.back());
			aux.pop_back();
		}		
	}
	
	g<<x.top().poz<<'\n';
	int nrcur=x.top().poz;
	k=0;
    for(i=n;i>=1;i--)
    {
        if(v[i].poz==nrcur)
        {
            s[++k]=v[i].val; nrcur--;          
        }
    }
	for(i=k;i>=1;i--)
		g<<s[i]<<" ";
	return 0;
}