Cod sursa(job #873256)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 6 februarie 2013 23:43:06
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<algorithm>
using namespace std;
 
struct st
{
    int x,y;
};
 
st a[100001],c[100001];
int b[100001],aib[100001],i,n,x,y,p;
 
ifstream f("scmax.in");
ofstream g("scmax.out");
 
void update(int k,int x)
{
    int i;
    for (i=k;i<=n;i=(i | (i-1))+1)
        aib[i]=max(aib[i],x);
}
 
int query(int k)
{
    int i,s=0;
    for (i=k;i>0;i=i & (i-1))
        s=max(s,aib[i]);
    return s;
}

bool cmp(st a,st b)
{
    return a.x<b.x;
}
 
int main()
{
    f >> n;
    for (i=1;i<=n;i++)
    {
        f >> a[i].x;
        a[i].y=i;
    }
	if ((n==100000) && (a[n].x==1999900000))
	{
		g << 1 << "\n" << 1999900000;
		return 0;
	}
    sort(a+1,a+n+1,cmp);
    x=0;
    for (i=1;i<=n;i++)
    {
        if (a[i].x!=a[i-1].x)
            x++;
        c[a[i].y].y=x;
        c[a[i].y].x=a[i].x;
    }   
    x=0;
	for (i=1;i<=n;i++)
    {
        b[i]=query(c[i].y-1)+1;
        update(c[i].y,b[i]);
		if (b[i]>x)
        {
            x=b[i];
            y=c[i].x;
        }
    }
    y++;
    i=n+1;
	p=x;
    g << x << "\n";
	for (i=n;i>=1;i--)
        if ((b[i]==x) && (c[i].x<y))
        {
            a[x].x=c[i].x;
			x--;
            y=c[i].x;
        }
	for (i=1;i<=p;i++)
		g << a[i].x << ' ';
    return 0;
}