Cod sursa(job #1654683)

Utilizator leopop29Pop Leonard leopop29 Data 17 martie 2016 12:50:44
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NM 100005
#define a first
#define b second

using namespace std;

vector< pair<int, int> > v;
int ai[NM*4], m = -1, r[NM];

void update(int p, int cl, int cr, int n)
{
    if(p < cl || p > cr)
        return;
    if(cl == cr)
    {
        if(cl == p)
            ai[n] = 1;
        return;
    }

    int m = (cl+cr)/2, nd = n*2;
    update(p, cl, m, nd);
    update(p, m+1, cr, nd+1);
    ai[n] = ai[nd]+ai[nd+1];
}

int querry(int ll, int lr, int cl, int cr, int n)
{
    if(ll > cr || lr < cl)
        return 0;
    if(ll <= cl && lr >= cr)
        return ai[n];

    int m = (cl+cr)/2, nd = n*2;

    return querry(ll, lr, cl, m, nd)+querry(ll, lr, m+1, cr, nd+1);
}

int main()
{
    ifstream f("scmax.in");
    ofstream cout("scmax.out");
    int n;

    f >> n;
    v.resize(n);
    for(int i = 0; i < n; ++i)
    {
        f >> v[i].a;
        v[i].b = (i+1);
    }
    sort(v.begin(), v.end());

    int e = 0;
    for(int i = 0; i < n; ++i)
    {
        if(v[i].a == v[i-1].a)
            ++e;
        update(v[i].b, 1, n, 1);

        int x = querry(1, v[i].b, 1, n, 1)-e;
        if(x > m)
        {
            m = x;
            int y = 0, z = 0;
            while(y < x)
            {
                while(v[z].a == v[z+1].a && z < i)
                    ++z;

                if(v[z].b <= v[i].b)
                {
                    r[y] = v[z].a;
                    ++y;
                    ++z;
                }
            }
        }
    }
    cout << m << '\n';
    for(int i = 0; i < m; ++i)
        cout << r[i] << ' ';
    return 0;
}