Cod sursa(job #2694983)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 11 ianuarie 2021 12:00:56
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int arr[MAXN], best[MAXN], fat[MAXN], n, k;
stack<int> sol;

void read()
{
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> arr[i];
}

void solve()
{
    k = 1;
    best[0] = 0;
    fat[0] = -1;
    for (int i = 1; i < n; ++i) {
        if (arr[i] > arr[best[k - 1]]) {
            fat[i] = best[k - 1];
            best[k++] = i;
        }
        else {
            int le = 0, ri = k - 1;
            while (le < ri) {
                int mid = le + (ri - le) >> 1;
                if (arr[i] == arr[best[mid]]) {
                    le = mid;
                    break;
                }
                if (arr[i] < arr[best[mid]])
                    ri = mid - 1;
                else
                    le = mid + 1;
            }
            fat[i] = (le == 0 ? -1 : best[le - 1]);
            best[le] = i;
        }
    }
}

void recursive_print(int pos)
{
    if (pos == -1)
        return;

    recursive_print(fat[pos]);
    fout << arr[pos] << ' ';
}

void print()
{
    fout << k << '\n';
    recursive_print(best[k - 1]);
}

int main()
{
    read();
    solve();
    print();
    return 0;
}

/**
5

a:24 12 15 15 19
b: 1  1  2  2  3
v:12 15 19

*/