Pagini recente » Cod sursa (job #1186104) | Cod sursa (job #875931) | Cod sursa (job #2971432) | Cod sursa (job #1823566) | Cod sursa (job #1267540)
#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;
}