Pagini recente » Cod sursa (job #2446002) | Cod sursa (job #2062994) | Cod sursa (job #2578835) | Cod sursa (job #2240512) | Cod sursa (job #1966246)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define zeros(x) ((-x)&(x))
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n;
int V[100005];
vector<int> NORM;
int PAR[100005];
struct q_{
int val, ind;
bool operator< (q_ a) const{
return val<a.val;
}
}AIB[100005];
void update(int x, q_ val){
for(int i=x;i<=n;i+=zeros(i))
AIB[i]=max(AIB[i],val);
}
q_ query(int x){
q_ r={0};
for(int i=x;i>=1;i-=zeros(i))
r=max(r,AIB[i]);
return r;
}
void read(){
in>>n;
for(int i=1;i<=n;i++)
in>>V[i];
}
void solve(){
for(int i=1;i<=n;i++)
NORM.push_back(V[i]);
sort(NORM.begin(),NORM.end());
for(int i=1;i<=n;i++){
int poz=lower_bound(NORM.begin(),NORM.end(),V[i])-NORM.begin()+1;
q_ q=query(poz);
update(poz,{q.val+1,poz});
PAR[poz]=q.ind;
}
int ind_max=query(n).ind;
vector<int> SOL;
while(ind_max){
SOL.push_back(ind_max);
ind_max=PAR[ind_max];
}
out<<SOL.size()<<"\n";
for(auto it=SOL.rbegin();it!=SOL.rend();it++)
out<<*it<<" ";
}
int main(){
read();
solve();
return 0;
}