# Cod sursa(job #2664891)

Utilizator Data 29 octombrie 2020 17:43:22 Subsir crescator maximal 0 cpp-64 done Arhiva educationala 2.14 kb
``````#include <fstream>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
typedef long long ll;
const int NMAX = 100001;
int n, m, ma, UpdatePoz, pozmax, a[NMAX], d[NMAX], T[NMAX], vals[NMAX];
pair< int, int>aint[4 * NMAX];
vector<int> b;
void update(int nod, int l, int r, int poz, int val) {
if (l == r) {
aint[nod] = { val , UpdatePoz };
return;
}
int mj = (l + r) / 2;
if (poz > mj)
update(nod * 2 + 1, mj + 1, r, poz, val);
else
update(nod * 2, l, mj, poz, val);
if (aint[nod * 2 + 1].first < aint[nod * 2].first)
aint[nod] = aint[nod * 2];
else {
if (aint[nod * 2 + 1].first == aint[nod * 2].first) {
if(aint[nod * 2 + 1].second < aint[nod * 2].second)
aint[nod] = aint[nod * 2];
else
aint[nod] = aint[nod * 2 + 1];
}
else
aint[nod] = aint[nod * 2 + 1];
}
}
pair<int, int> query(int nod, int l, int r, int x, int y) {
if (l >= x && r <= y)
return {aint[nod].first, aint[nod].second};
int mj = (l + r) / 2;
pair<int, int> s1{ 0, 0 }, s2{ 0, 0 };
if (x <= mj)
s1 = query(nod * 2, l, mj, x, y);
if (y > mj)
s2 = query(nod * 2 + 1, mj + 1, r, x, y);
if (s1.first < s2.first)
aint[nod] = s2;
else
aint[nod] = s1;
}
void AfisSolutii(int poz) {
if (T[poz] == 0)
return;
AfisSolutii(T[poz]);
fout << vals[poz] << " ";
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
vals[i] = a[i];
b.push_back(a[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
pair<int, int> sol;
for (int i = 1; i <= n; ++i) {
if (a[i] - 1 >= 1)
sol = query(1, 1, n, 1, a[i] - 1);
else {
sol.first = 0;
sol.second = 1;
}
d[i] = sol.first + 1;
T[i] = sol.second;
UpdatePoz = i;
update(1, 1, n, a[i], d[i]);
}
for (int i = 1; i <= n; ++i) {
if (ma < d[i]) {
pozmax = i;
ma = d[i];
}
ma = max(ma, d[i]);
}
fout << ma << "\n";
AfisSolutii(pozmax);
fout << "\n";
return 0;
}

``````