Question

Se considera numarul n si un vector v cu n elemente.
Construiti vectorul sol, cu următoarea semnificaţie: sol[i] va reţine numărul de subşiruri de elemente consecutive, ordonate strict crescător, care se termină cu i. Calculati suma tuturor elementelor vectorului sol.

Answer 1

Tocmai am realizat ca sol[i] retine subsirurile pana in POZITIA i si nu pana la valoarea i . Problema a devenit astfel simpla ;)

===================================================

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 100005;

int n, sol_final = 1;
int v[NMAX], sol[NMAX];
vector<pair<int,int>> perechi;

int main()
{
    int suma;

    cin >> n;
    for(int i=1; i<=n; i++) cin >> v[i];

    for(int i=1; i<=n; i++) perechi.push_back(make_pair(v[i], i));
    sort(perechi.begin(), perechi.end());

    for(auto x : perechi) {
        suma = 0;
        for(int j=1; j<=x.second; j++) {
            if(x.first == v[j]) continue;
            else suma += sol[j];
        }
        sol[x.second] = 1 + suma;
    }

    for(int i=2; i<=n; i++) {
        sol[i] += sol[i-1];
        sol_final += sol[i];
    }

    cout << sol_final << '\n';
}