Pagini recente » Cod sursa (job #1800319) | Cod sursa (job #691766) | Cod sursa (job #873323) | Cod sursa (job #1821624) | Cod sursa (job #3165854)
#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 << " ";
}
}