Cod sursa(job #2483800)

Utilizator rd211Dinucu David rd211 Data 30 octombrie 2019 12:13:37
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100003;
int A[NMAX],best[NMAX],poz[NMAX];
pair<int,int> arb[2*NMAX];
int n;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
void update(int index,int value)
{
    index+=n;
    arb[index].second=value;
    while(index)
    {
        index/=2;
        if(arb[2*index].second>arb[2*index+1].second)
        {
            arb[index] = arb[2*index];
        }
        else
        {
            arb[index] = arb[2*index+1];
        }
    }
}
pair<int,int> query(int left,int right)
{
    pair<int,int> maximum = {-1,-19231};
    left+=n;
    right+=n;
    while(left<right)
    {
        if(left%2)
        {
            if(maximum.second<arb[left].second)
            {
                maximum = arb[left];
            }
            left++;
        }
        if(right%2)
        {
            right--;
            if(maximum.second<arb[right].second)
            {
                maximum = arb[right];
            }
        }
        left/=2,right/=2;
    }
    return maximum;
}
void construct()
{
    for(int i = n-1;i>0;i--)
        arb[i]=max(arb[2*i],arb[2*i+1]);
}
int main()
{
    construct();
    int maxim = 1,p=n;
    fin>>n;
    for(int i = 1;i<=n;i++)
    {
        fin>>A[i];
        arb[i+n-1].first = i;
    }
    best[n]=1;
    update(n-1,1);
    poz[n]=-1;
    for(int i = n-1;i>=1;i--)
    {
        best[i]= 1;
        poz[i]=-1;
        int j = query(i,n).first;
        if(A[i]<A[j] && best[i]<best[j]+1)
        {
            best[i] = best[j]+1;
            update(i-1,best[j]+1);
            poz[i]=j;
            if(best[i]>maxim)
            {
                maxim = best[i];
                p = i;
            }
        }
    }
    vector<int> r;
    while(p!=-1)
    {
        r.push_back(A[p]);
        p = poz[p];
    }
    fout<<r.size()<<'\n';
    for(int i = 0;i<r.size();i++)
    fout<<r[i]<<" ";
    return 0;
}