Articole


Downloads


Links


Documentaţie


Despre infoarena


--------------------------------------------------------------------------------


Monitorul de evaluare


Trimite soluţii


Contul meu

.


! Cautare



In curand...

34741 membri inregistrati

13:10:14



Participa si tu la concursul Monthly 2014



Fii un bun infoarenaut! Implică-te!









Pagini recente » Contul meu | Profil miha5092 | Monitorul de evaluare | Borderou de evaluare (job #1235844) | Cod sursa (job #146356)

Cod sursa(job #146356)


Utilizator
filipbFilip Cristian Buruiana filipb
Data
1 martie 2008 16:30:31

Problema
Subsir crescator maximal
Scor
Ascuns

Compilator
cpp
Status
done

Runda

Marime
1.06 kb

Raporteaza aceasta sursa





?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMax 100005

int N, Res[NMax], v[NMax], lst[NMax], D[NMax], AIB[NMax], bst, up[NMax];

void update(int x, int ind)
{
    for (; x <= N; x += x^(x-1) & x)
        if (D[ind] > D[AIB[x]])
            AIB[x] = ind;
}

int query(int x)
{
    int mx = 0;

    for (; x; x -= x^(x-1) & x)
        if (D[AIB[x]] > D[mx])
            mx = AIB[x];
    return mx;
}

int main(void)
{
    int i, h = 1;

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

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
    {
        scanf("%d", &v[i]);
        Res[i] = lst[i] = v[i];
    }

    sort(lst+1, lst+N+1);
    for (i = 2; i <= N; ++i)
        if (lst[i] != lst[h])
            lst[++h] = lst[i];

    for (i = 1; i <= N; ++i)
        v[i] = lower_bound(lst+1, lst+h+1, v[i])-lst;

    for (i = 1; i <= N; ++i)
    {
        up[i] = query(v[i]-1);
        D[i] = D[up[i]] + 1;
        update(v[i], i);
    }

    for (i = 1; i <= N; ++i)
        if (D[bst] < D[i])
            bst = i;

    printf("%d\n", D[bst]);
    for (h = 0, i = bst; i; i = up[i])
        lst[++h] = Res[i];

    for (i = h; i; --i)
        printf("%d ", lst[i]);
    printf("\n");

    return 0;
}