Cod sursa(job #1477516)

Utilizator ballsMingiuci balls Data 26 august 2015 14:43:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <algorithm>

using namespace std;
typedef int var;

typedef int arr[150000];
arr V, SCM, T, Map, I;

#define zeros(a) (a&-a)

void update(int poz, int val) {
    if(poz == 0) return;
    for(;poz<150000; poz += zeros(poz))
        T[poz] = max(T[poz], val);
}
int query(int poz) {
    int r = 0;
    for(;poz;poz-=zeros(poz))
        r = max(r, T[poz]);
    return r;
}

#define isdigit(c) (c>='0'&&c<='9')
void read(int &a) {
    char c;
    #define gc getchar_unlocked
    for(c=gc(); !isdigit(c); c=gc());
    for(a=0; isdigit(c); a=(a<<1)+(a<<3)+c-'0', c=gc());
}

int main() {
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    int n, i, e=1, start = 0, val = 0;

    read(n);
    for(i=1; i<=n; i++)
        read(V[i]), I[i]=i;

    sort(I+1, I+n+1, [](int a, int b) {return V[a] < V[b];});
    for(i=1; i<=n; i++) {
        if(V[I[i]] != V[I[i-1]]) val++;
        Map[I[i]] = val;
    }

    for(start=0, i=1; i<=n; i++) {
        val = Map[i];
        SCM[i] = query(val - 1) + 1;
        if(SCM[start] < SCM[i]) start = i;
        update(val, SCM[i]);
    }

    printf("%d\n", SCM[start]);
    T[1]=V[start];
    for(int i=start-1; i; i--) {
        if(SCM[i]==SCM[start]-1&&V[i]<V[start])
            T[++e]=V[i], start=i;
    }
    while(e) printf("%d ", T[e--]);

    return 0;
}