Cod sursa(job #1163287)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 1 aprilie 2014 11:58:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int lsb(int nr)
{
    return ((nr)&(-nr));
}

int aib[100005];

void update(int where,int val)
{
    int i;
    for (i=where;i<100003;i+=lsb(i))
        aib[i]=max(aib[i],val);
}

int query(int where)
{
    int i,mx;
    mx=0;
    for (i=where;i>0;i-=lsb(i))
        mx=max(mx,aib[i]);
    return mx;
}

int i,n,nr,last,mx,l,mxl,vl[100005],sz,iv;
vector <pair<int,int> > v;
vector <int> rv,r,v2;
char s[2000005];

int main(void)
{
    FILE * f;
    f=fopen("scmax.in","r");
    ofstream g("scmax.out");
    fscanf(f,"%d",&n);
    fgets(s,20,f);
    fgets(s,2000003,f);
    sz=strlen(s);
    iv=0;
    for (i=0;i<sz;i++)
    {
        if ((s[i]>='0')&&(s[i]<='9'))
            nr=nr*10+s[i]-'0';
        else
        {
            v.push_back(make_pair(nr,iv));
            v2.push_back(nr);
            rv.push_back(nr);
            nr=0;
            iv++;
        }
    }
    sort(v.begin(),v.end());
    nr=1;
    v2[v[0].second]=nr;
    for (i=1;i<v.size();i++)
    {
        if (v[i].first!=v[i-1].first)
            nr++;
        v2[v[i].second]=nr;
    }
    for (i=0;i<v.size();i++)
    {
        nr=v2[i];
        mx=query(nr-1);
        l=mx+1;
        vl[i]=l;
        if (l>mxl)
            mxl=l;
        update(nr,l);
    }
    i=n;
    while (vl[i]!=mxl)
        i--;
    last=i;

    r.push_back(rv[last]);

    for (;i>0;i--)
    {
        if ((vl[i]==vl[last]-1)&&(v2[i]<v2[last]))
        {
            r.push_back(rv[i]);
            last=i;
        }
    }
    if (v2[i]<v2[last])
        r.push_back(rv[i]);

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