Cod sursa(job #2542585)

Utilizator sipdavSipos David Oliver sipdav Data 10 februarie 2020 11:08:22
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

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

const int dim = (int) (1e5) + 1;
const int oo = (int) (1e9);

struct inf
{
    int l, poz;
}arb[2 * dim];

int n, v[dim], a, b, pr[dim], lmax, l[dim];
inf mx;

inf maxim(inf a, inf b)
{
    if(a.l > b.l)
        return a;
    return b;
}

void update(int nod, int a, int b, inf val)
{
    if(a == b && arb[nod].l < val.l)
    {
        arb[nod] = val;
        return;
    }
    int mij = (a + b) / 2;
    if(a <= mij) update(2 * nod, a, mij, val);
    else update(2 * nod + 1, mij + 1, b, val);
    arb[nod] = maxim(arb[2 * nod], arb[2 * nod + 1]);
}

void query(int nod, int a, int b, int i)
{
    if(a >= 1 && b < i)
    {
        if(mx.l < arb[nod].l && v[arb[nod].poz] <= v[i])
            mx = arb[nod];
        return;
    }
    int mij = (a + b) / 2;
    if(a <= mij) query(2 * nod, a, mij, i);
    if(b > mij) query(2 * nod + 1, mij + 1, b, i);
}

void read()
{
    in>>n;
    inf val;
    val.l = 1;
    for(int i = 1;i <= n;i++)
    {
        in>>v[i];
        val.poz = i;
    }
}

void solve()
{
    mx.l = -oo;
    mx.poz = 0;
    query(1, 1, n, 3);
    out<<mx.l;
}

int main()
{
    read();
    solve();
    return 0;
}