Cod sursa(job #3261091)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 4 decembrie 2024 13:49:20
Problema Subsir crescator maximal Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>
using namespace std;

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

pair<int, int> tree[400001];
pair<int, int> sortedNums[100001];

set<int> selectedNums;

int neighbours[100001], a[100001], sortedNumsLen;

pair<int, int> findMaxLen(int left, int right, int currentNode, int pos) {
    if (left > pos) {
        return {0, 0};
    } else if (right <= pos) {
        return tree[currentNode];
    }
    return max(findMaxLen(left, (left + right) / 2, currentNode * 2, pos), findMaxLen((left + right) / 2 + 1, right, currentNode * 2 + 1, pos));
}

void update(int left, int right, int currentNode, int newLen, int pos) {
    if (right < pos || left > pos) {
        return;
    } else if (left == right) {
        tree[currentNode] = {newLen, pos};
        return;
    }
    update(left, (left + right) / 2, currentNode * 2, newLen, pos);
    update((left + right) / 2 + 1, right, currentNode * 2 + 1, newLen, pos);
    tree[currentNode] = max(tree[currentNode * 2], tree[currentNode * 2 + 1]);
}

void output(int pos) {
    if (neighbours[pos] == 0) {
        fout << a[pos] << ' ';
        return;
    }
    output(neighbours[pos]);
    fout << a[pos] << ' ';
}

int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    for (int i = n; i >= 1; --i) {
        if (selectedNums.count(a[i]) == 0) {
            sortedNums[++sortedNumsLen] = {a[i], i};
            selectedNums.insert(a[i]);
        }
    }
    sort(sortedNums + 1, sortedNums + sortedNumsLen + 1);
    int ansLen = 0, lastPos = 0;
    for (int i = 1; i <= sortedNumsLen; ++i) {
        pair<int, int> p = findMaxLen(1, n, 1, sortedNums[i].second - 1);
        neighbours[sortedNums[i].second] = p.second;
        update(1, n, 1, p.first + 1, sortedNums[i].second);
        if (p.first + 1 > ansLen) {
            ansLen = p.first + 1;
            lastPos = sortedNums[i].second;
        }
    }
    fout << ansLen << '\n';
    output(lastPos);
    return 0;
}