Pagini recente » Cod sursa (job #1563202) | Cod sursa (job #100699) | Cod sursa (job #135754) | Cod sursa (job #1934121) | Cod sursa (job #3288866)
#include <algorithm>
#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;
const int nmax = 1e5;
struct FenwickTree {
public:
FenwickTree(int n) : n(n) { fill(ind, ind + n + 1, -1); }
void update(int pos, int value, int idx) {
for (; pos <= n; pos += pos & (-pos)) {
if (value > aib[pos]) {
aib[pos] = value;
ind[pos] = idx;
}
}
}
pair<int, int> query(int pos) {
int ans = 0, idx = -1;
for (; pos > 0; pos -= pos & (-pos)) {
if (aib[pos] > ans) {
ans = aib[pos];
idx = ind[pos];
}
}
return {ans, idx};
}
private:
int n, aib[nmax + 1], ind[nmax + 1];
};
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, a[nmax + 1], cpy[nmax + 1], prv[nmax + 1];
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i];
cpy[i] = a[i];
}
// 1. normalizam vectorul
sort(cpy + 1, cpy + n + 1);
int m = unique(cpy + 1, cpy + n + 1) - (cpy + 1);
unordered_map<int, int> norm;
for (int i = 1; i <= m; i++) {
norm[cpy[i]] = i;
}
// 2. calculam folosind un aib
FenwickTree aib(m);
int ans = 0, poz = -1;
for (int i = 1; i <= n; i++) {
auto best = aib.query(norm[a[i]] - 1);
aib.update(norm[a[i]], best.first + 1, i);
prv[i] = best.second;
if (ans < best.first + 1) {
ans = best.first + 1;
poz = i;
}
}
// 3. reconstruirea
vector<int> result;
while (poz != -1) {
result.push_back(a[poz]);
poz = prv[poz];
}
reverse(result.begin(), result.end());
fout << result.size() << '\n';
for (auto x : result)
fout << x << ' ';
return 0;
}