Cod sursa(job #1668404)

Utilizator Bodo171Bogdan Pop Bodo171 Data 29 martie 2016 19:38:14
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include<deque>
using namespace std;
int aib[100005],best[100005],i,n,mx=0,index,val,var,aux[100005];
deque<int> vect;
struct key
{
    int a,b;
}v[100005];
bool comp(key x,key y)
{
    if(x.a==y.a) return x.b<y.b;
    return x.a<y.a;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int x)
{
    for(i=x;i<=n;i+=lbit(i))
        aib[i]++;
}
int compute(int x)
{
    int sum=0;
    for(i=x;i>0;i-=lbit(i))
        {sum+=aib[i];}

    return sum;
}
int main()
{
ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for(i=1;i<=n;i++)
{
    f>>v[i].a;
    v[i].b=i;
    aux[i]=v[i].a;
}
v[0].a=-1;
sort(v+1,v+n+1,comp);mx=0;
for(int contor=1;contor<=n;contor++)
    {
       if(v[contor].a!=v[contor-1].a)
   {best[v[contor].b]=compute(v[contor].b);
   update(v[contor].b);}

    if(best[v[contor].b]>mx)
    {
        mx=best[v[contor].b];
        index=v[contor].b;
    }}

g<<mx+1<<'\n';val=(1<<30);
for(i=index;i>=1;i--)
{
   if(best[i]==mx && aux[i]<val)
   {
       val=aux[i];
       vect.push_front(val);
       mx--;
   }
}
for(i=0;i<=vect.size()-1;i++)
    g<<vect[i]<<' ';
    return 0;
}