Cod sursa(job #1143569)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 15 martie 2014 18:09:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int aib[100005],v[100005],k[100005];
int n,i,nr,q,mx,last,mxn;
vector <pair <int,int> > axv1;
vector <int> r,axv,axv2;
int lsb(int nr)
{
    int ax=((nr)&(-nr));
    return ax;
}
int query(int pos)
{
    int mx=0;
    for (int i=pos;i>0;i-=lsb(i))
        mx=max(mx,aib[i]);
    return mx;
}
void update(int val,int pos)
{
    for (int i=pos;i<=mxn;i+=lsb(i))
        aib[i]=max(aib[i],val);
}
int main(void)
{
    FILE * f;
    f=fopen("scmax.in","r");
    ofstream g("scmax.out");
    fscanf(f,"%d",&n);

    for (i=1;i<=n;i++)
    {
        fscanf(f,"%d",&nr);
        axv1.push_back(make_pair(nr,i-1));
        axv.push_back(nr);
        axv2.push_back(nr);
    }
    sort(axv1.begin(),axv1.end());

    nr=1;
    axv2[axv1[0].second]=nr;
    //axv2.push_back(make_pair(axv1[0].second,nr));
    for (i=1;i<axv1.size();i++)
    {
        for (;(i<axv1.size())&&(axv1[i-1].first==axv1[i].first);i++)
            //axv2.push_back(make_pair(axv1[i].second,nr));
            axv2[axv1[i].second]=nr;
        nr++;
        //axv2.push_back(make_pair(axv1[i].second,nr));
        axv2[axv1[i].second]=nr;
    }
    mxn=nr;
    //sort(axv2.begin(),axv2.end());

    for (i=0;i<axv2.size();i++)
    {
        nr=axv2[i];
        q=query(nr-1);
        v[i]=nr;
        k[i]=q+1;
        if (q+1>mx)
            mx=q+1;
        update(q+1,nr);
    }

    last=2000000002;

    //for (i=0;i<=n;i++)
    //    cout<<k[i]<<' ';
    //cout<<'\n';
    //for (i=0;i<=n;i++)
    //    cout<<v[i]<<' ';

    for (i=n-1;i>=0;i--)
        if ((k[i]==mx)&&(v[i]<last))
        {
            r.push_back(i);
            mx--;
            last=v[i];
        }

    g<<r.size()<<'\n';
    for (i=r.size()-1;i>=0;i--)
        g<<axv[r[i]]<<' ';
    return 0;
}