Pagini recente » Cod sursa (job #519493) | Cod sursa (job #1422687) | Borderou de evaluare (job #201301) | ONI 2017, Clasele 11-12 | Cod sursa (job #1122410)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 100005
using namespace std;
vector <pair <int, int> > v;
vector <int> s;
int n, x, sol, aib[nmax], dp[nmax];
int sum(int idx) {
int ret = 0;
while(idx) {
ret += aib[idx];
idx -= idx & (-idx);
}
return ret;
}
void add(int pos, int val) {
while(pos < nmax) {
aib[pos] += val;
pos += pos & (-pos);
}
}
bool cmp(pair <int, int> a, pair <int, int> b) {
if(a.first == b.first) return (a.second > b.second);
return (a.first < b.first);
}
bool cmpInd(pair <int, int> a, pair <int, int> b) { return (a.second < b.second); }
int main() {
ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for(int i=0; i<n; i++) {
f>>x;
v.push_back(make_pair(x, i+1));
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<n; i++) {
dp[v[i].second] = sum(v[i].second) + 1;
if(i+1 < n && v[i].first != v[i+1].first) add(v[i].second, 1);
}
for(int i=1; i<=n; i++) sol = max(sol, dp[i]);
g<<sol<<"\n";
sort(v.begin(), v.end(), cmp);
for(int i=n-1; i>=0; i--)
if(dp[v[i].second] == sol) {
s.push_back(v[i].first);
sol--;
}
for(int i=int(s.size())-1; i>=0; i--) g<<s[i]<<" ";
g<<"\n";
return 0;
}