Cod sursa(job #1892323)

Utilizator gabrielamoldovanMoldovan Gabriela gabrielamoldovan Data 24 februarie 2017 21:26:55
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>


#define nmax 100005

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n, a[nmax], arbint[4*nmax], pos, val;
int k, sir[nmax];

int minim(int a, int b)
{
    if(a>b) return b;
    else return a;
}

void Add(int nod, int st, int dr)
{
    if(st==dr)
    {
        arbint[nod]=val;
        return ;
    }
    int div=(st+dr)/2;
    if(div>=pos) Add(2*nod, st, div);
    else Add(2*nod+1, div+1, dr);
    arbint[nod]=minim(arbint[2*nod], arbint[2*nod+1]);
}

void citire()
{
    f>>n;
    for(int i=1; i<=n; ++i)
    {
        f>>a[i];
        pos=i;
        val=a[i];
        Add(1, 1, n);
    }
}

void Query(int nod, int st, int dr)
{
    if(st==dr)
    {
        return ;
    }
    int div=(st+dr)/2;
    if(arbint[2*nod+1]>arbint[nod])
    {
        sir[++k]=arbint[2*nod+1];
    }
    Query(2*nod, st, div);
    Query(2*nod+1, div+1, dr);
}

int main()
{
    citire();
    sir[++k]=arbint[1];
    Query(1, 1, n);
    g<<k<<"\n";
    for(int i=1; i<=k; ++i)
    {
        g<<sir[i]<<" ";
    }
    return 0;
}