Cod sursa(job #1122410)

Utilizator h2g2Ford Prefect h2g2 Data 25 februarie 2014 18:01:13
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#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;
}