Cod sursa(job #1267540)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 20 noiembrie 2014 00:00:54
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int v[100001], sorted[100001], norm[100001], aib[100001], parent[100001], dp[100001], Q[100001];
int n, p;
 
inline int nr_de_0(int x) {
    int nr = 0;
    while(x % 2 == 0) {
        x >>= 1;
        nr++;
    }
    return nr;
}
 
inline int pow_doi(int exp) {
    int rez = 1, i;
    for(i = 1; i <= exp; i++) {
        rez <<= 1;
    }
    return rez;
}
 
int compar(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
 
int caut_bin(int val) {
    int l = 1, r = n, mid, ans = -1;
    while(l <= r) {
        mid = l + (r-l) / 2;
        if(sorted[mid] >= val) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}
 
int aib_query(int poz) {
    int maxim = 0;
    while(poz > 0) {
        if(dp[aib[poz]] > dp[maxim]) maxim = aib[poz];
        poz -= pow_doi(nr_de_0(poz));
    }
    return maxim;
}
 
// am modificat dp[i] in main
// pun pe pozitia norm[i] (+ toate mai mari din aib) valoarea i (daca dp[i] > dp[aib[poz]])
void aib_update(int i) {
    int poz = norm[i];
    while(poz <= n) {
        if(dp[aib[poz]] < dp[i]) aib[poz] = i;
        poz += pow_doi(nr_de_0(poz));
    }
 
}
 
int main() {
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    int i, p, last = 0;
 
    scanf("%d", &n);
    for(i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        sorted[i] = v[i];
    }
    sort(sorted + 1, sorted + n + 1);
    // construiesc vectorul normalizat
    for(i = 1; i <= n; i++) {
        norm[i] = caut_bin(v[i]);
    }
 
    for(i = 1; i <= n; i++) {
        p = aib_query(norm[i] - 1);
 
        dp[i] = 1 + dp[p];
        parent[i] = p;
        if(dp[i] > dp[last]) last = i;
 
        aib_update(i);
    }
 
    while(dp[last] != 0) {
        Q[++Q[0]] = v[last];
        last = parent[last];
    }
 
    printf("%d\n", Q[0]);
    for(i = Q[0]; i > 0; i--)
        printf("%d ", Q[i]);
    return 0;
}