HackerEarth Panda and Shopping problem solution

In this HackerEarth Panda and Shopping problem solution, Panda loves to shop! And well, anyone who loves to shop gets a huge amount of happiness even after a tiring session of window shopping.

There are N shops, all aligned linearly having index 1,2,3...N. Buying any positive number of items from a shop Si gives happiness equal to Hi. Unfortunately due to some unavoidable circumstances, every shop owner has introduced a value Li. You are credited Hi happiness from the ith shop if and only if this is the first shop you are buying something from or you buy at least one item from this shop and the last shop you shopped from was Sj such that Lj <= Li and j < i. Find the maximum sum of happiness that can be obtained following the rules given above!

HackerEarth Panda and Shopping problem solution.

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

typedef long long LL;

#define PII       pair<int,int>
#define all(c)    c.begin(),c.end()
#define sz(c)     (int)c.size()
#define clr(c)    c.clear()
#define pb        push_back
#define mp        make_pair
#define cin(x)    scanf("%d",&x)
#define MOD     1000000007
#define EPS     1E-10

const int maxn = 200000;
int H[maxn];
LL L[maxn];
LL segtree[4 * maxn];

void update(int idx , LL val , int l , int r , int pos)
{
    if(l > idx or r < idx) return ;
    if(l == r)
    {
        if(val > segtree[pos])
            segtree[pos] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(idx , val , l , mid , 2*pos);
    update(idx , val , mid+1, r , 2*pos + 1);
    segtree[pos] = max(segtree[2*pos] , segtree[2*pos + 1]);
}

LL query(int lQ, int rQ, int l, int r,int pos)
{
    if(l > rQ or r < lQ or l > r) return 0;
    else if(l >= lQ && r <= rQ) return segtree[pos];
    int mid = (l + r) >> 1;
    return max(query(lQ,rQ,l,mid,2*pos) , query(lQ,rQ,mid+1,r,2*pos+1));
}

int main()
{
    int n;
    cin >> n;
    vector< pair<LL,int> > arr(n);
    for(int i = 1; i <= n; i++)
    {
        cin >> H[i] >> L[i];
        arr[i-1].first = L[i];
        arr[i-1].second = i;
    }
    sort(all(arr));
    LL ans = 0;
    for(int i = 0; i < sz(arr); i++)
    {
        int idx = arr[i].second;
        LL val = query(1,idx - 1,1,n,1);
        val += H[idx];
        val = max(val , 0LL);
        ans = max(ans , val);
        update(idx , val , 1 , n , 1);
    }
    cout << ans << "\n";
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define ll              long long int
#define MOD             1000000007
#define si(a)           scanf("%d", &a)
#define sl(a)           scanf("%lld", &a)
#define pi(a)           printf("%d", a)
#define pl(a)           printf("%lld", a)
#define pn              printf("\n")
ll pow_mod(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}
ll h[100005], l[100005], tmp_l[100005];
ll dp[100005];
map < ll, ll > mp;
ll tree[4 * 100005];
void update_tree(int node, int lft, int rgt, int idx, ll res) {
    if(lft == rgt) {
        tree[node] = res;
        return;
    }
    int mid = (lft + rgt) >> 1;
    if(idx <= mid) {
        update_tree(2 * node, lft, mid, idx, res);
    } else {
        update_tree(2 * node + 1, mid + 1, rgt, idx, res);
    }
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
ll query_tree(int node, int lft, int rgt, int l, int r) {
    if(lft > rgt || l > rgt || r < lft) {
        return (ll)(-1e18);
    }
    if(lft >= l && rgt <= r) {
        return tree[node];
    }
    int mid = (lft + rgt) >> 1;
    ll res1 = query_tree(2 * node, lft, mid, l, r);
    ll res2 = query_tree(2 * node + 1, mid + 1, rgt, l, r);
    return max(res1, res2);
}
int main() {
    int n;
    si(n);
    assert(n >= 1 && n <= 100000);
    int cnt = 0;
    for(int i = 0; i < 4 * n; ++i) {
        tree[i] = LONG_LONG_MIN;
    }
    for(int i = 0; i < n; ++i) {
        sl(h[i]);
        sl(l[i]);
        tmp_l[i] = l[i];
        assert(h[i] >= (ll)(-1e5) && h[i] <= (ll)(1e5));
        assert(l[i] >= 1 && l[i] <= (ll)(1e18));
    }
    sort(tmp_l, tmp_l + n);
    for(int i = 0; i < n; ++i) {
        if(mp.find(tmp_l[i]) == mp.end()) {
            mp[tmp_l[i]] = cnt;
            cnt += 1;
        }
    }
    dp[0] = h[0];
    update_tree(1, 0, n - 1, mp[l[0]], dp[0]);
    for(int i = 1; i < n; ++i) {
        dp[i] = max(h[i], query_tree(1, 0, n - 1, 0, mp[l[i]]) + h[i]);
        update_tree(1, 0, n - 1, mp[l[i]], dp[i]);
    }
    ll res = LONG_LONG_MIN;
    for(int i = 0; i < n; ++i) {
        res = max(res, dp[i]);
    }
    pl(res);
    pn;
    return 0;
}