Cod sursa(job #2449523)

Utilizator voyagerSachelarie Bogdan voyager Data 19 august 2019 23:16:14
Problema Subsir crescator maximal Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.14 kb
#!/usr/bin/env python3

import sys
sys.stdout = open('scmax.out', 'w')

with open('scmax.in', 'r') as f:
    N = int(f.readline())

    bit = [0] * (N + 1)
    def update(i, ind):
        while i <= N:
            if dp[ind] > dp[bit[i]]:
                bit[i] = ind
            i += i & -i
    def query(i):
        mx = 0
        while i > 0:
            if dp[bit[i]] > dp[mx]:
                mx = bit[i]
            i -= i & -i
        return mx

    up, dp, norm = [-1] * N, [0] * N, [0] * N
    vv = sorted((x, i + 1) for i, x in enumerate(map(int, f.readline().split())))
    v = []
    for i, x in enumerate(vv):
        if i and x[0] == vv[i - 1][0]:
            pass
        else:
            v.append(x)
    del(vv)

    for p, x in enumerate(v):
        norm[x[1] - 1] = p + 1
    
    i = 0
    for x in norm:
        if not x: continue

        up[i] = query(x - 1)
        dp[x] = dp[up[i]] + 1
        update(x, i)
        i += 1

    bst = 0
    for x in range(N):
        if dp[x] > dp[bst]:
            bst = x

    print(dp[bst])
    i, sol = bst, []
    while i:
        sol.append(str(v[i][0]))
        i = up[i]
    print(' '.join(reversed(sol)))