Cod sursa(job #2830428)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 9 ianuarie 2022 21:30:23
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int NMAX=100005;
const int inf=2e9+5;

int N, dp[NMAX], v[NMAX], sol, nxt=inf;
struct segTree{
    int mx[4*NMAX]={}, lenmax[4*NMAX]={};
    void buildMax(int nod, int st, int dr)
    {
        if(st==dr){
            mx[nod]=v[st];
            return;
        }
        int mij=(st+dr)/2;
        buildMax(nod*2,st,mij);
        buildMax(nod*2+1,mij+1,dr);
        mx[nod]=max(mx[nod*2],mx[nod*2+1]);
    }
    void updateLen(int nod, int st, int dr, int poz, int val)
    {
        if(st==dr){
            lenmax[nod]=val;
            return;
        }
        int mij=(st+dr)/2;
        if(poz<=mij)
            updateLen(nod*2,st,mij,poz,val);
        else
            updateLen(nod*2+1,mij+1,dr,poz,val);
        lenmax[nod]=max(lenmax[nod*2],lenmax[nod*2+1]);
    }
    int queryLen(int nod, int st, int dr, int poz)
    {
        if(mx[nod]<v[poz] and dr<poz)
            return lenmax[nod];
        if(st==dr or st>=poz)
            return 0;
        int mij=(st+dr)/2;
        return max(queryLen(nod*2,st,mij,poz),queryLen(nod*2+1,mij+1,dr,poz));
    }
};
segTree a;

void afisare(int poz)
{
    if(poz==0 or sol==0)
        return;
    if(dp[poz]==sol and v[poz]<nxt){
        nxt=v[poz];
        sol--;
        afisare(poz-1);
        fout<<v[poz]<<' ';
    }
    else
        afisare(poz-1);
}

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>v[i];
    a.buildMax(1,1,N);

    dp[1]=1;
    sol=1;
    a.updateLen(1,1,N,1,1);
    for(int i=2;i<=N;i++){
        dp[i]=1+a.queryLen(1,1,N,i);
        sol=max(sol,dp[i]);
        a.updateLen(1,1,N,i,dp[i]);
    }

    fout<<sol<<'\n';

    afisare(N);

    fin.close();
    fout.close();
    return 0;
}