Cod sursa(job #2497039)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 21 noiembrie 2019 23:21:02
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <stdio.h>
	
#include <assert.h>
	
#include <algorithm>
	
#include <iostream>
	
using namespace std;
	
 
	
const int Nmax = 100005;
	
 
	
int n;
	
// initial vector | sorted vector with unique elements | normalized vector (norm[i] = pozition of v[i] in the sorted vector
	
int v[Nmax], vu[Nmax], norm[Nmax];
	
// aib tree | length of max sequence | trace path vector
	
int aib[Nmax], l[Nmax], t[Nmax];
	
 
	
inline int get_step(int x) {
	
    int k = 0;
	
    int result = 1;
	
    while (x % 2 == 0) {
	
        x >>= 1;
	
        ++k;
	
    }
	
 
	
    for (int i = 1; i <= k; ++i)
	
        result <<= 1;
	
    return result;
	
}
	
 
	
// Singura diferent este cum calculez 2^(nr de zerouri terminale)
	
void update(unsigned int idx, int i) {
	
    for (; idx <= n; idx += (idx & (~idx + 1)))
	
        if (l[i] > l[aib[idx]])
	
            aib[idx] = i;
	
}
	
 
	
int query(unsigned int idx) {
	
    int maxx = 0;
	
    for (; idx; idx -= (idx & (~idx + 1)))
	
        if (l[maxx] < l[aib[idx]])
	
            maxx = aib[idx];
	
    return maxx;
	
}
	
 
	
int bsearch(int* a, int n, int x) {
	
    int pos = 0;
	
    int pas = 1 << 17;
	
    while (pas >>= 1)
	
        if (pos + pas <= n && a[pos + pas] < x)
	
            pos += pas;
	
    return pos + 1;
	
}
	
 
	
int main() {
	
    freopen("scmax.in", "r", stdin);
	
    freopen("scmax.out", "w", stdout);
	
    int m = 1, best = 0;
	
 
	
    scanf("%d", &n);
	
    for (int i = 1; i <= n; ++i) {
	
        scanf("%d", &v[i]);
	
        norm[i] = vu[i] = v[i];
	
    }
	
    
	
    sort(vu + 1, vu + n + 1);
	
    for (int i = 1; i <= n; ++i)
	
        norm[i] = bsearch(vu, n, v[i]);
	
 
	
    for (int i = 1; i <= n; ++i) {
	
        t[i] = query(norm[i] - 1);
	
        l[i] = l[t[i]] + 1;
	
        update(norm[i], i);
	
        if (l[i] > l[best])
	
            best = i;
	
    }
	
 
	
 
	
    printf("%d\n", l[best]);
	
    for (m = 0; best; best = t[best])
	
        vu[++m] = v[best];
	
    for (int i = m; i; --i)
	
        printf("%d ", vu[i]);
	
 
	
    return 0;
	
}