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


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;
}