Cod sursa(job #2359508)

Utilizator dacianouaPapadia Mortala dacianoua Data 28 februarie 2019 21:35:07
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#define nmax 100000
#define dim 10000
using namespace std;
int poz,n,here;
pair<int,int> v1[nmax+5],v2[nmax+5];
vector<int> ans;
int arb[4*nmax+5];
char buff[dim+5];
FILE *fin=fopen("scmax.in","r");
FILE *fout=fopen("scmax.out","w");
int compare(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.first==p2.first)
        return p1.second>p2.second;
    return p1.first<p2.first;
}
int maxv(int x,int y)
{
    return x>y?x:y;
}
void quicksort(int left,int right)
{
    int i=left,j=right;
    pair<int,int> temp,mij=v1[(left+right)>>1];
    while(i<=j)
    {
        while(compare(v1[i],mij))
            i++;
        while(compare(mij,v1[j]))
            j--;
        if(i<=j)
        {
            temp=v1[i];
            v1[i]=v1[j];
            v1[j]=temp;
            i++;
            j--;
        }
    }
    if(left<j)
        quicksort(left,j);
    if(right>i)
        quicksort(i,right);
}
void read(int &nr)
{
    nr=0;
    while(buff[poz]<'0' || buff[poz]>'9')
        if(++poz==dim)
        fread(buff,1,dim,fin),poz=0;
    while(buff[poz]>='0' && buff[poz]<='9')
    {
        nr=nr*10+buff[poz]-'0';
        if(++poz==dim)
            fread(buff,1,dim,fin),poz=0;
    }
}
void update(int poz,int val,int nod,int st,int dr)
{
    if(st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mid=(st+dr)>>1,tmp;
    if(poz>mid)
        update(poz,val,(nod<<1)+1,mid+1,dr);
    else
        update(poz,val,nod<<1,st,mid);
    tmp=arb[nod];
    arb[nod]=maxv(arb[nod<<1],arb[(nod<<1)+1]);
    if(arb[nod]>tmp && nod==1)
        here=poz;
}
int query(int l,int r, int nod,int st,int dr)
{
    if(st>=l && dr<=r)
        return arb[nod];
    int mid=(st+dr)>>1,sol=-1;
    if(mid>=l)
        sol=maxv(sol,query(l,r,nod<<1,st,mid));
    if(mid<r)
        sol=maxv(sol,query(l,r,(nod<<1)+1,mid+1,dr));
    return sol;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(v1[i].first),v1[i].second=i,v2[i]=v1[i];
    quicksort(1,n);
    for(int i=1;i<=n;i++)
        update(v1[i].second,query(1,v1[i].second,1,1,n)+1,1,1,n);
    fprintf(fout,"%d\n",arb[1]);
    cout<<here;
    for(int i=here,j=0;j<arb[1];)
        if(i!=here && v2[i].first>=ans[ans.size()-1])
        i--;
        else
        ans.push_back(v2[i].first),j++,i--;
    for(int i=ans.size()-1;i>=0;i--)
        fprintf(fout,"%d ",ans[i]);
    return 0;
}