Cod sursa(job #1590310)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 4 februarie 2016 21:21:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define NMax 100005

using namespace std;
struct date {int x, y;} best[4*NMax];
int start, sfarsit, i, val, poz, maxcurent, c[NMax], N, cost, sol[NMax], pozitie;
date Max(date a, date b)
{
    if(a.x<b.x) return b;
    return a;
}
void Update (int nod, int st, int dr)
{
    if(st==dr)
    {
        best[nod].x=val;
        best[nod].y=poz;
        return;
    }
    int m=(st+dr)/2;
    if(poz<=m)
        Update(2*nod, st, m);
        else Update(2*nod+1, m+1, dr);
    best[nod]=Max(best[2*nod],best[2*nod+1]);
}
void Interog (int nod, int st, int dr)
{
    if(c[best[nod].y]>cost)
    {
        if(maxcurent<best[nod].x) maxcurent=best[nod].x, pozitie=best[nod].y;
        return;
    }
    else if (st==dr) return;
    int m=(st+dr)/2;
    if(start<=m) Interog(2*nod,st,m);
    if(m<sfarsit) Interog(2*nod+1,m+1,dr);

}
void Dinamica()
{
    int i;
    val=1; poz=N; cost=c[N];
    Update(1,1,N);
    sol[N]=-1;
    for(i=N-1;i>=1;--i)
    {
        start=i+1; sfarsit=N; cost=c[i]; maxcurent=0; pozitie=0;
        Interog(1,1,N);
        sol[i]=pozitie;
        val=maxcurent+1; poz=i; cost=c[i];
        Update(1,1,N);
    }
}
void Afisare()
{
    int i=best[1].y;
    cost=0;
    while(i>=-1&&cost<best[1].x)
    {
        printf("%d ",c[i]);
        i=sol[i];
        cost++;
    }
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    scanf("%d",&N);
    for(i=1;i<=N;i++)
        scanf("%d ",&c[i]);
    Dinamica();
    printf("%d\n",best[1].x);
    Afisare();
    return 0;
}