Cod sursa(job #3165854)

Utilizator ScipexRobert Chiri Scipex Data 7 noiembrie 2023 08:14:32
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n;
int a[100001];

int lsb(int x) {
    return (x & (-x));
}

struct Arb {
    int v[400010];

    void ins(int poz, int x, int st = 1, int dr = n, int idx = 1) {
        if (st == dr) {
            v[idx] = poz;
            return;
        }

        int mij = (st + dr) / 2;
        if (poz <= mij) {
            ins(poz, x, st, mij, idx * 2);
        } else {
            ins(poz, x, mij + 1, dr, idx * 2 + 1);
        }

        v[idx] = max(a[v[idx * 2]], a[v[idx * 2 + 1]]);
    }

    void get(int p1, int p2, int& mx, int x, int st = 1, int dr = n, int idx = 1) {
        if (st == dr) {
            if (a[v[idx]] < x && a[v[idx]] > mx) {
                mx = v[idx];
            }
            return;
        }

        int mij = (st + dr) / 2;
        if (p1 <= mij) {
            get(p1, p2, mx, x, st, mij, idx * 2);
        }
        if (mij < p2) {
            get(p1, p2, mx, x, mij + 1, dr, idx * 2 + 1);
        }
    }
} mx;

int idx[100001], l[100001], lmax, idxmx;

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
        mx.ins(i, a[i]);
    }
    l[1] = 1;
    lmax = 1;
    idxmx = 1;

    for (int i = 2; i <= n; i++) {
        int imx = 0;
        mx.get(1, i - 1, imx, a[i]);
        l[i] = l[imx] + 1;
        idx[i] = imx;

        if (l[i] > lmax) {
            lmax = l[i];
            idxmx = i;
        }

        // cout << i << " " << imx << " " << l[imx] << "\n";
    }

    fout << lmax << "\n";
    vector<int> v(lmax);
    for (int i = lmax - 1; i >= 0; i--) {
        v[i] = a[idxmx];
        idxmx = idx[idxmx];
    }
    for (int x : v) {
        fout << x << " ";
    }
}