Cod sursa(job #1138411)

Utilizator span7aRazvan span7a Data 9 martie 2014 23:30:17
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int k,n,i,nrcur;
struct vec
{
    int val,poz;    
};
vec v[100005];
int s[100005];
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;
void solve()
{
	 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();
        }       
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {   f>>k;
        v[i].val=k;
       solve();
    }
     
    g<<x.top().poz<<'\n';
     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;
}