HackerEarth One Girl One Sequence problem solution

In this HackerEarth One Girl One Sequence problem solution, You are given a sequence of distinct integers a1, a2, …, an and an integer x and you have to perform the following operations:

Remove the current minimum from a. This operation costs x.

Remove the current maximum from a. This operation costs the number of elements located on the right to the maximum. Formally, if the maximum is ai and the current size of the sequence is k, then the cost will be k – i

What is the minimum cost to erase the whole sequence?

HackerEarth One Girl One Sequence problem solution.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define lb(a) ((a)&(-(a)))
#define int ll

const int maxn = 1e6 + 20;

int a[maxn] , b[maxn] , pos[maxn] , l[maxn] , fen[maxn];

void add(int p , int val)
{
    for(p += 5; p < maxn; p += lb(p))
        fen[p] += val;
}

int get(int p)
{
    int res = 0;
    for(p += 5; p > 0; p -= lb(p))
        res += fen[p];

    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n , X;
    cin >> n >> X;

    for(int i = 0; i < n; i++)
        cin >> a[i] , b[i] = a[i];

    sort(b , b + n);
    for(int i = 0; i < n; i++)
    {
        a[i] = lower_bound(b , b + n , a[i]) - b;
        pos[a[i]] = i;
    }

    int inv = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        l[pos[i]] = get(pos[i]);
        add(pos[i] , 1);
        inv += l[pos[i]];
    }

    int res = 1e18;
    for(int i = 0; i <= n; i++)
    {
        res = min(res , i * X + inv);
        inv -= l[pos[i]];
    }

    cout << res << endl;
}

Second solution

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
//#define long long int
using namespace std;
const int maxn = 1e6 + 20, maxv = 100, mod = 1e9 + 7, maxa = 1005, maxs = 820, maxb = 23, base = 737, base2 = 3079, mod3 = 1e7 + 19, delt = 10513;
const long long inf = 2e16;
const int infint = 1e9 + 11;
long long max(long long x, long long y){return (x > y ? x : y);}
long long min(long long x, long long y){return (x < y ? x : y);}

int a[maxn];
int dp[maxn][2];
int num[maxn];
vector <int> v;
int fen[maxn];

void add(int ind, int val)
{
    ind++;
    while(ind < maxn)
    {
        fen[ind] += val;
        ind += (ind) & (-ind);
    }
}

int get(int ind)
{
    ind++;
    int sum = 0;
    while(ind > 0)
    {
        sum += fen[ind];
        ind -= (ind) & (-ind);
    }
    return sum;
}

int32_t main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++)
    {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        num[a[i]] = i;
    }
    add(num[n - 1], 1);
    for(int i = n - 2; i >= 0; i--)
    {
        dp[i][0] = min(dp[i + 1][0], dp[i + 1][1]) + x;
        int tmp = get(num[i]);
        dp[i][1] = dp[i + 1][1] + tmp;
        add(num[i], 1);
    }
    cout << min(dp[0][0], dp[0][1]) << endl;
}

coding problems solutions