Cod sursa(job #690372)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 25 februarie 2012 16:23:26
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <stdio.h>
#define maximul(a,b) ((a>b)?a:b)
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

long long n,i,maxim,j,mmaxim=0,pmax;
long long v[200005],prec[200005],s[200005],A[200005],Apoz[200005];

void update(int nod, int stanga,int dreapta,int poz,int val)
{
    if(stanga==dreapta)
        A[nod]=val,Apoz[nod]=poz;
    else
    {
        int mijloc = (stanga+dreapta)/2;
        if(poz<=mijloc)
            update(2*nod,stanga,mijloc,poz,val);
        else
            update(2*nod+1,mijloc+1,dreapta,poz,val);
        if(A[2*nod]>A[2*nod+1]) A[nod]=A[2*nod],Apoz[nod]=Apoz[2*nod];
        else A[nod]=A[2*nod+1],Apoz[nod]=Apoz[2*nod+1];
    }
}

int querry(int nod,int left,int right,int a,int b,int diferit)
{
    if(a<=left && right<=b)
        if(v[Apoz[nod]]<v[diferit])
            return nod;
        else
            return 0;
    int mijloc=(left+right)/2,i1=0,i2=0;
    if(a<=mijloc) i1=querry(2*nod,left,mijloc,a,b,diferit);
    if(b>mijloc) i2=querry(2*nod+1,mijloc+1,right,a,b,diferit);
    if(A[i1]>A[i2]) return Apoz[i1];
    else return Apoz[i2];
}

void afis(int nodul)
{
    if(prec[nodul]) afis(prec[nodul]);
    g<<v[nodul]<<' ';
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i];
    prec[1]=0;
    s[1]=1;
    i=2;
    update(1,1,n,1,1);
    while(i<=n)
    {
        /*maxim=0;
        for(j=i-1;j>=1;j--)
            if(v[i]>v[j] && (!maxim || s[maxim]<s[j]))
                maxim=j;*/
        maxim = querry(1,1,n,1,i-1,i);
        if(!maxim)
            s[i]=1,prec[i]=0,update(1,1,n,i,1);
        else
            s[i]=s[maxim]+1,prec[i]=maxim,update(1,1,n,i,maxim+1);
        if(s[mmaxim]<s[i]) mmaxim = i;
        i++;
    }
    g<<s[mmaxim]<<'\n';
    afis(mmaxim);
	f.close();
	g.close();
	return 0;
}