Cod sursa(job #1202205)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 27 iunie 2014 12:05:48
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<fstream>
#include<algorithm>
using namespace std;
using namespace std;
ifstream f("scmax.in");
ofstream o("scmax.out");

int a[100100],b[401000],c[102000],d[102000],n,best[100100],last,sol=0,f1[100010];
void sortq(int l,int r){
    int m=a[(l+r)/2],i=l,j=r;
    do{
        while(m>a[i])i++;
        while(m<a[j])j--;
        if(i<=j){
            swap(c[i],c[j]);
            swap(a[i],a[j]);
            j--;
            i++;
        }
    }while(i<=j);
    if(i<r)sortq(i,r);
    if(j>l)sortq(l,j);
}

int qeury(int p,int q,int l,int r,int nod){
     if(p>q)return 0;
     if(l>=p && q>=r)return b[nod];
     int m = (r+l)/2,sol=0;
     if(m>=p) sol = max(sol,qeury(p,q,l,m,2*nod));
     if(m+1<=q) sol = max(sol,qeury(p,q,m+1,r,2*nod+1));
     return sol;
}

void update(int q,int v,int l,int r,int nod){
if(l==r){b[nod] = v; return;}
int m = (l+r)/2;
if(m>=q) update(q,v,l,m,nod*2);
else update(q,v,m+1,r,nod*2+1);
b[nod] = max(b[nod*2],b[nod*2+1]);
}

int main(){
f>>n;
for(int i=1;i<=n;i++)f>>a[i],c[i]=i,d[i]=a[i];
sortq(1,n);
int l=1, val = a[1];
for(int i=2;i<=n;i++)
   if(val==a[i])f1[c[i]]=l;
  else {
    f1[c[i]]=++l;
    val = a[i];
  }


int lung;
for(int i=n;i;i--){
    lung = qeury(f1[i]+1,n,1,n,1);
    best[i] = lung +1;
    if(best[i]>sol){
        sol=best[i];
        last = i;
    }
    update(f1[i],lung+1,1,n,1);
}
o<<sol<<"\n";
 val = d[last];
o<<d[last]<<" ";sol--;
for(int i=last+1;i<=n;i++)
     if(best[i]==sol  && d[i]>val){
        o<<d[i]<<" ";
        sol--;
        val = d[i];
     }
}