Cod sursa(job #1966246)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 15 aprilie 2017 01:07:25
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#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;
}