Pagini recente » Cod sursa (job #445733) | Istoria paginii runda/oni_2005/clasament | Cod sursa (job #353512) | Cod sursa (job #2707955) | Cod sursa (job #489654)
Cod sursa(job #489654)
/*9:29:00*/
#include <stdio.h>
#define S 100010
int n, X[S], N[S], AIB[S], st[S], P[S], R[S];
int compar(const void * a, const void * b) {
return X[(*((int *)a))] - X[(*((int *)b))];
}
void normalize(int n, int * X, int * N) { /* ret 1..n */
int i;
for (i=0;i<n;i++) {
R[i] = i;
}
qsort(R, n, sizeof(int), compar);
for (i=0;i<n;i++) {
N[R[i]] = i+1;
}
}
int search(int ind) {
int i;
int max;
i = ind;
while (X[R[i-1]]==X[R[ind-1]]) i--;
max = AIB[i];
while (i>0) {
if (max<AIB[i]) max = AIB[i];
i -= ( i ^ (i - 1) ) & i;
}
return max;
}
int add(int i, int val) {
while (i<=n) {
if (AIB[i]<val) AIB[i] = val;
i += (i ^ (i-1)) & i;
}
}
void backwrite(int pos) {
if (pos!=-1) {
backwrite(P[pos]);
printf("%d ", X[pos]);
}
}
int main() {
int i, j;
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &n);
for (i=0;i<n;i++) scanf("%d", X+i);
normalize(n, X, N);
for (i=0;i<=n;i++) st[i] = -1;
for (i=0;i<n;i++) {
j = search(N[i]);
add(N[i], j+1);
P[i] = st[j];
if (st[j+1]==-1 || N[st[j+1]] > N[i]) st[j+1] = i;
}
j = search(n+1);
printf("%d\n", j);
backwrite(st[j]);
printf("\n");
return 0;
}