Pagini recente » Cod sursa (job #906856) | Cod sursa (job #2775219) | Cod sursa (job #18244) | Cod sursa (job #2233812) | Cod sursa (job #3261091)
#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;
}